Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For which limit ordinals α is it true that if G is a graph with vertex set α then G must have either an infinite path or independent set on a set of vertices with order type α?
Suppose G and H are Cayley, or vertex-transitive, expanders on the same number of vertices and can be matched with asymptotically vanishing edge distance. Must they be isomorphic?
There exists a positive absolute constant c such that, for any nonzero algebraic number α which is not a root of unity, M(α)≥ 1+c. Equivalently, there exists a positive absolute constant c such that, for any nonzero algebraic number α of…
Let G be a graph, let α(G) be its independence number, and let c(G) be the number of cut-vertices of G. Graffiti's cut-vertex conjecture. α(G) ≥ 1+c(G)/2 The paper verifies this inequality for the graph classes considered there using…
Problem 3: Find a class C3 of 4-uniform hypergraphs such that • the P4-structure of every graph with a balanced skew partition belongs to C3, • no odd ring belongs to C3, • C3 belongs to NP. 6http://www.cs.rutgers.edu/…
Let G be a graph with n vertices and minimum degree at least 2. The game domination number γ_g(G) is the number of moves in the domination game when Dominator starts and both players play optimally. The 1/2-conjecture. γ_g(G) ≤ ⌈ 1/2n ⌉.…
Let rgeqslant 2 and let n be the length of a word over a two-letter alphabet. An r-regular word is a word satisfying the corresponding regularity condition, and PTE(2^r+1,2,r) denotes the set of words representing Prouhet–Tarry–Escott…
Let G be a graph on n vertices, and let δ be the minimum vertex degree among all graphs in the LC orbit of G. Suppose that there is no graph G' on n vertices with Q(G',4)<Q(G,4). LC-orbit minimum-degree conjecture. Then there is no graph…
How accurately can local algorithms solve or approximate semidefinite programs, particularly SDP relaxations for random graph problems?
conjecture. Here the word asymptotically comes in two flavours, the qualitative result that the fibre of the map K(R)(p) \to Lf1 K(R)(p) is bounded above, and the quantitative refinement specifying a bound and perhaps also describing LT (1)…
Let D be a symmetric directed graph on m vertices, with corresponding adjacency matrix e_11 e_12 … e_1m e_21 e_21 … e_2m hdotsfor4 e_m1 e_m2 … e_mm . Kyle graph characterization conjecture. The graph D is a Kyle graph if and only if all of…
Do complete k-uniform hypergraphs admit Hamiltonian decompositions into tight cycles?
Let H be a Borel graph with finite asymptotic separation index, and let G_1 and G_2 be spanning Borel subgraphs of H. A set is a complete section for a graph if it meets every connected component, and a section is G_1-independent if it…
Does there exist a graph for which repeatedly passing to k-net graphs, at appropriately chosen scales, produces strictly smaller large-scale graph models unboundedly many times?
Problem Let k_1, …, k_p be positve integer Does there exists an integer g(k_1, …, k_p) such that every g(k_1, …, k_p)-strong tournament T admits a partition (V_1…, V_p) of its vertex set such that the subtournament induced by V_i is a…
Let G be a connected graph, let T be a well-covered tree, and let I(G,x) denote the independence polynomial of G. Levit–Mandrescu conjecture. If I(T,x)=I(G,x), then G is a well-covered tree. The conjecture concerns whether…
For positive integers n, let N_n(t) be the numerator polynomial in H'_n(t)=fracN_n(t)(1-t)^2n, and define S(m)=∑_(X,Y)∈ 2^[m]× 2^[m]|XmathbintriangleY|=m 2^2m-1, where 2^[m] is the power set of [m]. Symmetric-difference formula conjecture.…
Let G be a cycle on n≥ 3 vertices. Its dominion is the invariant denoted by ζ(G). Cycle dominion conjecture. If G is a cycle on n≥ 3 vertices, then ζ(G)= n^2+5n/6, if n ≡ 1pmod3 n, if n ≡ 2pmod3. The cases n≡ 1,2pmod3 are presented as…
For a bridgeless graph G, let S_p^d-1:=x∈R^d:lVertxrVert_p=1 be the unit p-sphere. The generalized S^2_p-flow conjecture. For every bridgeless graph G and every p∈[1,∞], φ_3,p(G)=2. This extends Jain's S^2-flow conjecture from the…
Let G(n,m) denote the collection of graphs on n vertices and m edges, and let β^FL_1(G) denote the first flag-complex Betti number of a graph G. Complete-bipartite spanning-subgraph conjecture. If G∈G(n,m) and…