Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let d_r(n) be the maximum, over all binary phylogenetic trees with n leaves, of the minimum number of r-state characters required to define the tree. Let n_r be the least integer N such that the Semple–Steel lower bound is attained for…
For a random graph of average degree d, what upper bound can constant-degree sum-of-squares prove on the size of an independent set. It is conjectured that the answer is C n/√d (for some constant C) even though the true size of the largest…
Let T be the set of positive integers under consideration in the paper, let T_1=22,58,70,82,142,190,298,330,358,382,478,658,742,862,1222,1978, and let C_3(t) denote the number of 5-cycles in the relevant graph associated with t. The…
For any ε>0, there is a constant C(ε)>0 such that, for any positive integers x, y, p, q satisfying x^pnot= y^q, the inequality |x^p-y^q| ≥ C(ε)maxx^p, y^q^1-(1/p)-(1/q)-ε holds.
Let G be a 2-connected 3-regular graph of order n, and let π_p(G) denote its path partition number. Reed's conjecture. The path partition number satisfies π_p(G)≤lceiln/10⌉. The source states that Yu recently settled this conjecture, so it…
Let G=⟨ S⟩ be a two-ended group, and suppose that its commutator subgroup satisfies G'≅ Z_p^n. The Hamiltonian circle conjecture. The Cayley graph Cay(G;S) has a hamiltonian circle. This extends the preceding result for one-ended Cayley…
Let (G_n) and (H_n) converge to the same graph limit, and let (T_n) be a convergent sequence with each T_n a spanning tree of G_n. Do there exist spanning trees P_n of H_n converging to the same limit as (T_n)?
Let R_m,n denote the checkerboard graph whose vertices are the squares of an m× n checkerboard, with adjacency determined by the graph construction above. A graph derangement is a permutation of the vertices induced by an automorphism-free…
Let a,c,d,e be algebraic indeterminates, and define T(n,k) by T(n,k)=[a(n-k)+c]T(n-1,k-1)+(dk+e)T(n-1,k) for n≥ 1, with T(0,k)=δ_k0. Thus T=(T(n,k))_n,k≥ 0 is a lower-triangular matrix over Z[a,c,d,e]. A polynomial is nonnegative in the…
: Show that the jump number of a random linear extension of a grid poset (i.e., a product of chains) is close to the maximum w.h.p. (For the "symmetric grid" poset [m]^n, this is known for n = exp(o(log m)).)
For E_n:y^2=x^3-n^2x, is n a congruent number if and only if L(E_n,1)=0?
Let C_n be the cycle on n vertices, and let eppa(C_n) be its EPPA number. Cycle EPPA conjecture. If n≥ 7, then eppa(C_n)=nchoose 2. This conjecture asserts that the previously stated upper bound for the EPPA number of C_n is sharp. The…
Is the same binary quadratic Diophantine solvability problem NP-hard under randomized reductions?
Let L be a Latin square of order n, and let χ( L) denote the chromatic number of its Latin square graph. Then The chromatic-number conjecture. Every Latin square L satisfies χ( L) ≤ n+1 if n is odd, n+2 if n is even. For n≤ 8 this bound is…
Let Γ be a directed graph, let tildeΓ be a k-cover of Γ, let v be a vertex of Γ, and let tildev be a lift of v in tildeΓ. If the edge weights of Γ are indeterminates, then the polynomial fracA_tildev(tildeΓ)A_v(Γ) has positive…
A hat-chain is the graph constructed by joining the indicated complete graphs and paths, as in the hat-chain construction preceding the conjecture; an expression is e-positive when its chromatic symmetric function has a nonnegative…
For each minimum degree δ≥4, let f(δ) and f'(δ) denote the two repetition ratios defined in the paper for the diameter problem under the relevant clique- or chromatic-number condition. Repetition-ratio conjecture. For every δ≥4,…
Let A be a simple Abelian variety of dimension g over a number field K embedded in R. Denote by ℓ the rank over Z of the Mordell-Weil group A(K). For any ε>0, there exists h_0>0 (which depends only on the Abelian variety A, the real number…
Let n≥ 2, and let v_1,…,v_2^n-1∈F_2^n be nonzero, not necessarily distinct, vectors satisfying ∑_i=1^2^n-1v_i=0. Balister et al.'s partition conjecture. There exists a partition of F_2^n into pairs of vectors p_i,q_i, for i=1,…,2^n-1, such…
Given a panhandle matroid that can be realized as a lattice path matroid on a n × k grid, is it true that the coeffcients of the Ehrhart polynomial are bounded above by the coefficients of the uniform matroid U_n,k and below by those of…