Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let Q^d denote the d-dimensional hypercube, and call a graph stackable if, starting with one cup at each vertex, all cups can be moved onto any prescribed target vertex according to the cup-stacking rules. Cube stackability conjecture. For…
Is there a graph of chromatic number ℵ_1 such that for all ε>0 if n is sufficiently large and H is a subgraph on n vertices then H contains an independent set of size >n^1-ε?
For stochastic chemical reaction networks, determine how to certify that a computed probability landscape is accurate, quantify the best attainable accuracy for laptop-scale and large-scale computation, and control errors such as missed…
Suppose G=(V,E) is a finite, connected, simple graph. For x,y∈ V, let S(x,y) be the set of self-avoiding walks from x to y, and let S(u_i,v_j) denote the corresponding set on G× K_2. Self-avoiding-walk bunkbed question. Is it true that for…
Let π:S[0,1]→Z_≥0 interpret a binary word as an integer, and let u_1<u_2<…<u_k_n be the ordered elements of π(U_n). Define p_n:Z_≥1→[0,∞), g↦frac#i| u_i+1-u_i=gk_n-1. Let μ_g(n) be the mean of the probability measure p_n. Gap-distribution…
Let Q_k be the k-dimensional hypercube graph (so that Q_k has 2^k vertices and k2^k-1 edges). Determine the behaviour of ex(n;Q_k).
Is the Yao-Yao Graph a t-spanner for constant t? A geometric graph is a t-spanner (or just a spanner) if, for every pair of nodes, the shortest distance between the nodes following the edges of the graph is at most t times the Euclidean…
Let G be a regular graph of even order. The 1-factorization conjecture. Every regular graph of even order with sufficiently high degree is 1-factorizable. Here, 1-factorizable means that the edge set of G can be decomposed into perfect…
Can one decide in deterministic polynomial time whether x^2-dy^2=-1 has an integral solution?
All graphs are finite, simple, and undirected; for a graph G, let V(G) be its vertex set and let d(v) denote the degree of v. A linear forest is a forest in which every component is a path. If G has minimum degree at least 2, then Akbari…
Let S be a commutative semigroup with 0, and let G(S) be its zero-divisor graph. A graph is uniquely complemented if it is complemented and any two complements of the same vertex have equal neighborhoods. A vertex has a unique complement…
Let f_r(n) be minimal such that every graph on n vertices with ≥ f_r(n) edges and chromatic number ≥ r contains a triangle. Determine f_r(n).
Let A⊂ R^2 be an infinite set for which there exists some ε>0 such that in any subset of A of size n there are always at least ε n with no three on a line. Is it true that A is the union of a finite number of sets where no three are on a…
A heroic family of graphs is one for which there is a constant d(H)>0 such that every H-free graph has cochromatic number less than d(H). Let K be a complete graph and let t be a positive integer; the family in question consists of K and…
Let T) be a tree of order n ≥ 2. A subtree root is a zero of the subtree polynomial of T. Define D_n=z∈Ccolon |z|≤ 1+√[n-1]n-1. Disk conjecture. The subtree roots of T lie in D_n. This strengthens the proved bound for all trees by making…
Given a prime p, can a generator of (Z/pZ)^* be found in deterministic polynomial time?
Test and analyze whether deleting extra points and fixing the lift x↦ x^p improves Frobenius lifts for nondegenerate curves.
This naturally raises the question: can one improve this bound if G is far from being a disjoint union of cliques? Neverthe- less, the conjecture of Alon, Bollobás, Krivelevich and Sudakov remains wide open. For many years, it was a…
Induced packing and covering Let H be a fixed graph, G an n-vertex graph. If the minimum number of edges needed to add or remove from G in order to remove all induced copies of H is o(n^2), then the regularity lemma implies that the…
Are there deletion-contraction formulas for the polymatroid Tutte polynomial?