Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let p be an odd prime satisfying 3nmid p-1, let F_p be the field with p elements, and let G(λ,X^3+a) denote the associated cubic equational graph over F_p, with λ ranging over N_p and a∈ F_p^*. Cubic connectedness conjecture. Almost all…
Let the n-Roberts graph encode the facet adjacencies of the n-cube, and let a hinged spanning cycle be a spanning cycle of this graph whose corresponding 2n facet adjacencies are retained as hinges while all other ridges are removed.…
A graph G is Z_3-flow-critical if it is flow-critical with respect to nowhere-zero Z_3-flows, as defined in the source. Density conjecture for Z_3-flow-critical graphs. Every Z_3-flow-critical graph G satisfies |E(G)|≤ 3|V(G)|-5. Moreover,…
For which 0∈ D⊆ F_p is it true that any A⊂ F_p^n avoiding x,x+y,x+2y∈ A with y∈ D^n∖0 has size ≤ C^n for some C < p?
For integers n and d with 2≤ d≤ n-2, let m(n,d) be the minimum number m such that every bridgeless graph of order n and size at least m has an orientation of diameter at most d. Conjecture on m(n,d). m(n,d)=n-dchoose 2+n+2. The formula is…
Question Is the chromatic number of a random lift of K_5 concentrated on a single value?
Let G be a graph. A sequential decomposition of a digraph J is an ordered sequence of spanning subdigraphs H_1,H_2,… such that every arc of J belongs to exactly one H_i. The sequential decomposition conjecture. There is an orientation J of…
Let H(n) denote the number of Hadamard matrices of order n. If a Hadamard matrix of order n exists, permuting its rows and columns already gives at least (n!)^2 distinct Hadamard matrices. The growth-rate conjecture. For any n=4m with m∈N,…
Does there exist a constant c such that \operatorname{mon-cr}(G)<c \operatorname{cr}(G) for every graph G?
Let d be a positive integer. A graph is d(d+1)-connected when deleting fewer than d(d+1) vertices leaves it connected. The Lovász–Yemini conjecture. If a graph is d(d+1)-connected, then it is rigid in R^d. This conjecture would extend…
Let C_10 find x satisfying x^e≡ apmod n under gcd(e,φ(n))=gcd(a,n)=1. Is complete integer factorization randomized polynomial-time reducible to C_10?
Let m be a positive integer, let ε be an m-th primitive root of unity, and let H(n,m) be the Hamming graph. Write H_1,…,H_m for possibly empty induced subgraphs whose vertex sets partition the vertices of H(n,m), and let Δ(H_i) denote the…
What properties of a graph H roughly determine its Ramsey number?
A primitive graph is a graph whose automorphism group acts primitively on its vertices, and its distance sequence records the distinct finite and infinite distances from a vertex. Let p be a prime. Prime-distance nonexistence conjecture.…
A linear forest is a graph whose connected components are paths, and the linear arboricity la(G) of a graph G is the minimum number of linear forests whose edge sets partition E(G). Let G be any graph with maximum degree Delta. Linear…
Let k≥ 2 be an integer and α_1,…,α_n be non-zero elements in a field K of zero characteristic, such that no quotient α_i/α_j with jnot=i is a root of unity. Consider the function F(X_1,…,X_k)= detpmatrix α_1^X_1 … α_k^X_1cr ⋮ ddots ⋮cr…
rmgon(G) ≤ |E(G)|-|V(G)|/2 + 2, where rmgon(G) the denotes the divisorial gonality of graph G.
Let D=(V,E) be a directed graph that is the union of two disjoint directed spanning trees. Can we characterize when does D have a directed spanning tree T ⊆ E such that E-T is also a directed spanning tree and reversing the orientation of…
For every convex polytope P of dimension d≥ 1, let L(P) be its face lattice and let G(L(P)) be its cover graph: the vertices are the faces of P, and two faces F and F' are adjacent exactly when one covers the other in L(P), equivalently…
Kahn's conjecture: given a rank-n matroid and bases B_{i,j} for 1\leqi,j\leqn, can one choose b_{i,j}\inB_{i,j} so that every column set {b_{1,j},\ldots,b_{n,j}} and every row set {b_{i,1},\ldots,b_{i,n}} is a basis?