Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let F be an exact clause-set, meaning that its deficiency is maximal among all clause-sets with the same conflict matrix or conflict multigraph. Suppose that the conflict matrix of F is the distance matrix of a connected graph. Generalised…
Let α be the generalized monotone-triangle enumeration, let A_n-1:=α(n-1;1,2,…,n-1), and let n≥ k≥4. Polynomial-ratio conjecture. There exist polynomials p_k(n) and q_k(n) satisfying deg p_k-deg q_k=k-3 and…
Is it true that if all vertices of a base polyhedron B are in 0,1,-1^n and 0 ∈ B, then B has a vertex v such that -v is also a vertex?
For fixed x,y≥ 1, let a_x,y,n denote the probability that the (x,y) edge-addition process on n vertices generates an (x,y) task-dependency graph. Edge-addition success-probability conjecture. lim_n→∞a_x,y,n=1. This conjecture is based on…
Let n be a nonnegative integer. Count the total number of parts across all partitions of n whose parts are odd, and separately the total number of parts across all partitions of n into distinct parts. A partition has exactly one even part…
Call an infinite connected graph G of uniformly bounded degree an infinite expander if there is a constant c>0 such that, for every vertex set S and every finite-radius ball B(r) satisfying |S∩ B(r)|<|B(r)|/2, one has |∂ S∩ B(r)|>c|S∩…
Conjecture 1 (Lei and Bai). If G is a Ricci-flat 5-regular graph, then G is either isomorphic to RF_72^5 or is a Cartesian product of the Petersen graph, the Triplex graph, or the dodecahedral graph with a cycle of length at least 6, or…
Let G be a connected graph. The invariant L(G) is the graph parameter measuring the contribution of leaves, and c(G) is the cyclomatic number of G. The vertex metric dimension bound conjecture. dim(G)≤ L(G)+2c(G). This extends the…
Gallai’s conjecture is still unsolved as of today, and has only been confirmed on very specific classes of graphs. Gallai’s path-decomposition conjecture Marthe Bonamy (joint work with Alexandre Blanché and Nicolas Bonichon)
Let G be an abelian group and let X⊆ G∖0. Call X simply orderable when its elements can be arranged so that every nonempty proper consecutive subsequence has nonzero sum. Costa–Morini–Pasotti–Pellegrini conjecture. If X is finite and has…
conjecture . . . . . . . . . . . . . . . . . . . . . . . . 45 Peter Nelson (joint with Carolyn Chun, James Dylan Douthitt, Wayne Ge, Tony Huynh, Matthew E. Kroeker) Rainbow triangles and the Erdős-Hajnal problem in projective geometries…
Can we find asymptotic results based on density, δ = dfrac|E| nchoose2 ? See Butler and Young paper (https://ajc.maths.uq.edu.au/pdf/57/ajc_v57_p065.pdf). Note: Z(G) = n - 0(n) for random graph G(n,p).
Let P_m denote the path on m vertices, and let tilder(P_a,P_b) denote the online Ramsey number for the pair of graphs P_a and P_b. Path Ramsey conjecture. For k≥ 4, lim_ℓ→∞fractilder(P_k+1,P_ℓ+1)ℓ=3/2. Moreover, for all integers ℓ≥ k≥ 4,…
Let V_c(g) be the maximum number of vertices of a graph of genus g embedded in a surface, and let b(g) be the stated upper bound for this quantity. For an integer S satisfying S≡ 1 or 3pmod 6, set g=(S-1)(S-3)/6. Super-maximization…
Estimate the maximum of F(A,B) as A,B range over all subsets of 1,…,N, where F(A,B) counts the number of m such that m=ab has exactly one solution (with a∈ A and b∈ B).
Is there a constant t such that every t-tough graph is Hamiltonian?
For a nonamenable group Γ, does the Bernoulli shift 0,1^Γ factor onto 0,1,2^Γ?
Let G be a graph. Write ξ(G) for its containability number, the minimum number of cops needed to contain the robber, c(G) for its cop number in the original Cops and Robbers game, and Δ(G) for its maximum degree. Containability bound. For…
Does every oriented graph have a vertex with at least as many vertices at distance 2 as at distance 1?
Question Is there a constant c such that every n-vertex K_t-minor-free graph has at most c^tn cliques?