Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then fracR(k)k2^k/2→ ∞.
Let l be a positive integer, and let G be an l-connected chordal graph. Let K_l+3 denote the complete graph on l+3 vertices. A clique root is a real root of the clique polynomial C(G,x). Clique-root conjecture. If G is K_l+3-free, then G…
: Is enumeration of pressing sequences of bicolored graphs (aka simple pseudographs) #P-hard? Is there an FPRAS for sampling them?
Let B be a curve of genus b\ge 2. A finite set S\subset\operatorname{Aut}(B) is good when the union of the graphs of its elements is a smooth divisor in B\times B, and define its packing number by \alpha=|S|/(b-1). What is the maximal…
Let G be a loopless graph of order n, and let k be a positive integer. A subgraph H of G is modulo k-regular if every vertex has degree divisible by k in H. Alon–Friedland–Kalai conjecture. If |E(G)|>(k-1)n, then G admits a modulo…
For every ε>0 and integer t≥1, is there N_0(t,ε) such that every A⊆[t]^N with N≥ N_0(t,ε) and |A|≥ε t^N contains a combinatorial line?
Conjecturally, every graph G satisfies both \chi(G)\leq\max_{v\in V(G)}\tfrac12\bigl(d(v)+1+\omega(G[\widetilde N(v)])\bigr) and \chi(G)\leq\max_{uv\in E(G)}\tfrac12\bigl(\gamma_\ell(u)+\gamma_\ell(v)\bigr), where…
For n≥1, let Q_n be the n-dimensional hypercube and let pmd(Q_n) denote its positive matching decomposition number. Hypercube formula. pmd(Q_n)=2n-1, for all n≥1. The source presents this assertion in a conjecture environment immediately…
Let X^D_S and X^D_B be the sets at levels S and B, let T⊂X^D_S be a valid subset, and let φ^D_(S,B) be the transformation between these levels. Write S(T) for the sum of the elements of a subset and let Ψ^D_B denote the corresponding…
Let P^alt_a be an alternating path, let S^sc_b be a start-central star, and let R_dih denote the corresponding dihedral Ramsey number. Dihedral Ramsey conjecture. For any a,b≥ 2, we have R_dih(P^alt_a,S^sc_b)=a+b-2-(abbmod 2). The…
Let S and T be balanced rooted binary phylogenetic X-trees, meaning that each has 2^m leaves for some non-negative integer m and height m, and let n=|X|. Write rm mast( S, T) for the maximum size of a common restriction that is an…
For every pair of integers t≥ 2 and s≥ 1, there exists a constant c=c(t,s) such that every graph G with no induced subgraph isomorphic to K_t,t and satisfying simw(G)≤ s also satisfies tree-α(G)≤ c. Equivalently, for each fixed t, bounded…
Let P_n be the supremum of the sizes of nondegenerate polynomial D(n)-tuples over Z[X]. Find an upper bound for P_n depending only on deg n, not on the coefficients of n.
Let d_ℓ(m) be the coefficient of x^ℓ in the Boros-Moll polynomial P_m(x). For a sequence a_i_i≥ 0, let Ra_i_i≥ 0=a_i+1/a_i_i≥ 0. A sequence is infinitely log-monotonic when every iterate has alternating log-concavity and log-convexity as…
Let T be a tree, and let D be an orientation of T. The Wiener index W(D) is the sum of the directed distances over all ordered pairs of vertices, where the distance is the length of a shortest directed path when one exists and is 0…
Let G be a graph on d vertices, embedded as in Theorem 1.3. Let n denote the girth of G, and suppose that d=2g+1+p and n-2≤ p. Minimal-cycle Betti-number conjecture. The property N_2,p fails, and β_n-2,n is equal to the number of cycles of…
Given a,b and a prime p with nonsingular curve y^2=x^3+ax+b, can a point on the curve modulo p be found in deterministic polynomial time?
Let G be a simple graph. Write Δ(G) for its maximum degree, and call G overfull if |E(G)|>Δ(G)⌊|V(G)|/2⌋. A graph is of Class 2 when its chromatic index satisfies χ'(G)=Δ(G)+1. Overfull Conjecture. Let G be a graph of Class 2 with…
Let G and overlineG be nontrivial connected graphs of order n≥ 8. Write rvd(G) for the rainbow vertex-disconnection number of G. Rainbow vertex-disconnection Nordhaus–Gaddum conjecture. rvd(G)+rvd(overlineG)≥ n. This conjecture proposes an…
Let K_n be the complete graph on n vertices whose edges are coloured with two colours. A collection of triangles is pairwise edge-disjoint if no edge belongs to more than one triangle. Erdős's conjecture. Every 2-coloured K_n contains…