Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For every integer g≥2, is there an n_0(g) such that whenever n>n_0(g) and n≡1 or 3pmod 6, there is a Steiner triple system on n vertices in which every collection of j triples spans at least j+3 vertices for each 2≤j≤g?
Let A=[A(n,k)]_n,k≥ 1 be the Eulerian triangle, where A(n,k) is the Eulerian number, and define its square by A^ulcorner=[A(n+k,k)]. Eulerian-square conjecture. The Eulerian square A^ulcorner is strictly totally positive: all its minors…
Let G be a finite simple connected graph, and let P(G) be its graph polytope. Write its Ehrhart series as Ehr(P(G),x)=∑_n≥ 0#W(G,n)x^n. Ju's conjecture. The polynomial in the numerator of this Ehrhart series is symmetric, also known as…
Conjecture (BEC-conjecture) If G_1 and G_2 are n-vertex graphs and (Δ(G_1) + 1) (Δ(G_2) + 1) < n + 1, then G_1 and G_2 pack.
Let Q_max(n,d) denote a maximum solution of the (n,d)-queens problem. Four-by-four board conjecture. For every integer d≥4, |Q_max(4,d)|=2^d. This is presented as the special case k=2 of the preceding upper-bound discussion and is related…
Is there A⊆ N such that lim_n→ ∞1_A* 1_A(n)/log n exists and is eq 0?
Let G be a graph, let D be a target, and let |D| denote the total demand of D. Write π(G,D) for the pebbling number of G with target D, and π_t(G) for the t-fold pebbling number. Weak Target Conjecture. Every graph G satisfies π(G,D)≤…
A stronger BSG theorem The standard BSG theorem is as follows: let E(A) = |(a,b,c,d)∈ A^4: a+b=c+d|. If E(A)/|A|^3≥ 1/K then there is a subset A'⊂ A so that |A'|≥ frac|A|K^100 and |A'+A'|≤ K^100|A'|. One of the drawbacks of BSG theorem is…
Let G be a 3-regular, 3-connected bipartite graph. Tutte's conjecture. Every such graph is Hamiltonian. The supplied text introduces this conjecture after noting that the known counterexamples to Tait's conjecture were not bipartite; its…
Let f(h,n) denote the number of n-vertex graphs with obstacle number at most h. The function g(n) satisfies g(n)∈ O(nlog^2 n). Obstacle-number graph-counting conjecture. The number of such graphs satisfies f(h,n)≤ 2^g(n)· o(h). An improved…
Let s_m,L denote the sum associated with the dual canonical bases of the tensor-product representation indexed by m and of length L, evaluated at q=1. Let c_n be the integer sequence A00902, specified by c_n=2c_n-1+(2n-2)c_n-2, with c_1=1…
Let s≥ 2 and n≥ 3, and let G=( P, L; I) be a generalized n-gon of order s, so its Levi graph is (s+1)-regular, has diameter n, and has girth 2n. Write p_s^(n)=s^n-1+s^n-2+…+s+1. Here C_k denotes a cycle of length k, and C_khookrightarrowG…
In combinatorics, the Cameron–Erdős conjecture (now a theorem) is the statement that the number of sum-free sets contained in [N]=1,…,N is O (2^N/2). The sum of two odd numbers is even, so a set of odd numbers is always sum-free. There are…
Let L_ciota_m,ν^B(n) denote the quantity defined in the paper for graphs on n vertices. Asymptotic conjecture. As n tends to infinity, L_ι_m,ν^B(n)~ 2log_2 n. The authors state that they feel certain this asymptotic relation is true; the…
Let G be a connected graph. Its density is d(G)=|E(G)|/|V(G)|-1. The graph G is uniformly dense if d(H)≤ d(G) for every connected subgraph H of G. A graph is cyclically orderable if it has a cyclic ordering of its edges such that every…
Let G be a bridgeless cubic graph. Fan–Raspaud conjecture. The graph G contains three perfect matchings M_1,M_2,M_3 such that no edge is covered by all three of them. The Berge–Fulkerson conjecture implies this conjecture, but the…
There exists some constant c>0 such that R(C_4,K_n) ≪ n^2-c.
Let P_n^k denote the kth power of the path graph on n vertices, and let G=P_n^kmathbinsquare…mathbinsquareP_n^k be the Cartesian product of m copies of P_n^k, with n≥ 4k+1. The leverage-centrality count conjecture. The number of distinct…
If there is no prime in the interval [n+1,n+k], then the product (n+1)…(n+k) has at least k distinct prime divisors.
Let B_r(x) denote the function used in the associated Stirling-number asymptotics, and let r be an integer with r≥ 1. Consider the power series about 0 of e^-x/(r+1)B_r(x). Non-negative coefficient conjecture. For each integer r≥ 1, this…