Problems
Everything in the archive: the problem as it was posed, what has been attempted against it, and who checked each attempt. The mark down the left of the list says who has looked — a person, a machine, or nobody yet. Human reviews and machine checks are counted separately and are never added together.
49 problems
Araujo, Piga and Schacht asked whether density and codegree both above 1/4 force a tight Hamilton cycle in a linearly quasirandom 3-graph. No: the threshold is p_0 = max_0 ≤ x ≤ 1minx^3, 1-x ≈ 0.3177, and below it there are dense 3-graphs…
Sivaraman asked whether perfect divisibility is characterized by its chromatic consequence: is a graph G perfectly divisible if and only if χ(H) ≤ binomω(H)+12 for every induced subgraph H of G? False: the Paley graph P(17) satisfies the…
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
For a forbidden configuration F, the Anstee-Sali conjecture predicts that forb(m, F) is Theta(m^(X(F)-1)), where X(F) comes from an explicit product construction. Disproved: the 4-uniform family on six vertices formed by a two-vertex core…
Reading computed the order dimension of the poset of regions for most finite Coxeter arrangements, observed that an exceptional type whose dimension exceeds its rank would be the first known simplicial arrangement with that property, and…
The near-quadratic Elekes-Ronyai expander conjecture over R predicts that a nonspecial polynomial expands any finite set to near-quadratic size. False: a fixed nonspecial quadratic polynomial, together with arbitrarily large finite sets of…
If a finite graph has girth at least five, must its minimum dual degree satisfy δ^*(G) ≤ -∂_n(G), where ∂_n(G) is the smallest eigenvalue of its distance matrix? The Hoffman-Singleton graph violates it: dual degree 7 against eigenvalue…
Monical, Tokcan and Yong conjectured that Schubitopes, the generalized permutahedra arising as Newton polytopes of Schubert polynomials and of Demazure characters of GL_n, are Ehrhart positive. Disproved by an explicit Schubitope whose…
For a bipartite graph without isolated vertices and with a unique minimum dominating set, does the proposed function m(n, γ) bound the number of edges whenever γ ≥ 2 and n ≥ 3γ? A 13-vertex bipartite graph with 22 edges exceeds the…
Mihail and Vazirani conjectured that the graph of every 0/1-polytope has edge expansion at least one. Disproved by a family of 0/1-polytopes whose edge expansion decreases exponentially in the dimension.
Must every connected graph satisfy the proposed upper bound on its independence number in terms of residue and largest induced-bipartite-subgraph order? The family overlineK_2r+1 ∨ (K_r sqcup K_r) violates it for every r ≥ 3.
If a chromatic symmetric function is Schur positive, must every finite-variable specialization X_G(x_1, …, x_k) have a saturated Newton polytope? A 12-vertex bipartite graph realizes weights (6,6,0) and (8,2,2) but omits their midpoint…
Chromatic quasisymmetric functions of natural unit interval graphs were conjectured to have log-concave coefficients in the elementary basis. A connected 13-vertex example refutes it: for the Hessenberg function…
Simon conjectured that every skeleton of a simplex is extendably shellable. False: for every d ≥ 3 there is a pure d-dimensional shellable simplicial complex that is not shelling completable.
An ℓ-Oddtown is a family of subsets of an n-element set whose set sizes are not divisible by ℓ while all pairwise intersection sizes are. Berlekamp and Graver showed the maximum size is n for prime ℓ, Babai and Frankl extended this to…
The paper constructs an exact cluster F⊆Z^2 of cardinality 8 with full affine span and an F-tiling whose orbit closure contains no 1-periodic F-tiling, giving a non-degenerate counterexample to Nivat's conjecture for non-convex windows.…
The target-free clique conjecture asserts that the supports of stable fixed points of a nondegenerate combinatorial threshold-linear network are exactly its target-free cliques, the bidirected cliques no outside vertex receives an edge…
Are the Kazhdan-Lusztig polynomials of matroids always unimodal - in particular log-concave, or even real-rooted, as conjectured? No: representable matroids obtained by deleting points from finite projective geometries have non-unimodal…
Is the difference between the numbers of positive and negative adjacency eigenvalues of every connected line graph at most one? A 14-vertex witness has signature 2, and chaining copies gives connected line graphs of signature k + 1 for…
Can a finite set of lattice points determine many rectangles but few isosceles triangles? Both parts of the governing question have negative answers, quantified by explicit blowup rates, and the resulting configurations give obstructions…