Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let m be the number of muffins, s the number of students, and let f(m,s) be the largest possible size of the smallest assigned muffin piece. Scaling conjecture. For all k,m,s∈N, f(km,ks)=f(m,s). This conjecture is solved; the paper states…
Given a graph G with a minimum zero forcing set of size s_0, determine the probability that a randomly chosen set S of size s ≥ s_0 is a forcing set.
Let G be a connected undirected graph, let s be a vertex of G, and let N be the set of neighbors of s, excluding s. For each nonempty subset W⊆ N, let overlineG_/W∪s denote the graph obtained by contracting W∪s in G and removing all loops.…
Let G be a connected loopless multigraph, and let g:= |E(G)| - |V(G)| + 1 denote its cyclomatic number. Brill–Noether gonality conjecture. Then dgon(G) ≤ lfloorg + 3/2⌋. This is the r=1 case of the Brill–Noether conjecture for finite…
Prove the simple construction from trapdoor groups with infeasible inversion to directed transitive signatures secure, or repair the construction.
Let k be a positive integer, and let (s^k)_n denote the corresponding power-sum sequence satisfying a linear recurrence (s^k)_n=∑_j=1c_j(q)(s^k)_n-j. Recurrence and coefficient conjecture. The linear recurrence corresponding to k has order…
Let F_2 be the free group on generators a and b, and let S⊂ F_2 be a shape. Say that S has finite filling when the solitaire filling process generated by S can fill only finitely many sites. A cyclic subgroup is a subgroup of the form ⟨…
For a symmetric edge polytope, can we obtain regular unimodular triangulations using liftings with low heights? If so, how many such triangulations can be obtained?
Let S be a peg-solitaire board, let D(S) be its set of legal-move vectors, and let B⊂D(S) be a basis of V(S,Q). Define V(B)=∑_f∈BZ·f. Let F(S,Z) denote the relevant integer lattice generated by the legal-move vectors. Doubled-basis…
A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise. Conjecture For every positive even integer n, the number of even latin squares of order n and the number of odd latin…
Let G be a connected graph, let A_G be its connected subgraph arrangement, and let χ(A_G) denote the characteristic polynomial of this arrangement. Integral-roots conjecture. The polynomial χ(A_G) has only integral roots if and only if A_G…
Let T be a tree. All-trees conjecture. Every tree T is odd prime. Paths, unions of paths, star graphs, and several additional classes are known to be odd prime, but the assertion for all trees remains open.
Let H be a graph with at least one edge. A subdivision of H is obtained by replacing edges of H with pairwise internally vertex-disjoint paths; let Sub(H) be the class consisting of K_2 and all subdivisions of H. A separating Sub(H)-system…
For k ≥ 2, let min S_sw^(k)(n) denote the minimal subword entropy among words of length n. Eventual monotonicity conjecture. There is a value N such that the function fracmin S_sw^(k)(n)n is increasing for n ≥ N. The function is known…
Let R be a commutative ring with unity. Define the annihilating ideal-graph AG(R) to have as vertices the nonzero ideals I with nonzero annihilator, meaning that there is a nonzero ideal J such that IJ=(0); distinct vertices I and J are…
Let G be a connected graph of order n, let L(G) denote the set of longest paths of G, and let f(G,P) denote the distance parameter for a subset P of longest paths. A function g is sublinear if g(n)/n→ 0 as n→∞. Sublinear-distance…
Let H be a graph with k vertices, and let R^ind(H) denote the minimum number of vertices of a graph G such that every red-blue edge-colouring of G contains an induced monochromatic copy of H. Erdős's conjecture. There exists a constant C>0…
Is it true that if an undirected graph G with terminal set T is 2k-element-connected, then it has a k-element-connected orientation?
Let H be a Kimura Hadamard matrix (KHM) of order 4(2k)+4, and let (R,S)∈Aut(H) be an automorphism of prime order p. Prime-order divisor conjecture. Then p=2 or p| k. The conjecture is suggested by all examples presented in the paper. Under…
Is every graph class defined by excluding one fixed tree as an induced subgraph χ-bounded?