Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks for a proof that the Ramsey number of a k-cycle against a complete graph on n vertices is k minus one times n minus one plus one, when k is at least n.
Determines the Ramsey number of a four-cycle against the star with n edges.
Asks for a proof that the three-color Ramsey number for two triangles and a complete graph on n vertices grows much faster than the two-color version.
Asks for a proof that the k-color Ramsey number of an odd cycle on two n plus one vertices is negligible against that of the triangle, for n at least two.
Determines the k-color Ramsey number of the even cycle on two n vertices.
Asks whether every 3-coloring of the edges of the complete graph on 4n - 3 vertices has a monochromatic cycle of length n, for every n > 3; the site's wording also includes the triangle, where it fails, and the bound is known for all large n.
Asks whether the k-color Ramsey number of any tree on n vertices is at most k times n plus a bounded amount.
Determines the k-color Ramsey number of the complete bipartite graph with s vertices in one class and t in the other.
Asks whether every graph on n vertices with bounded maximum degree has size Ramsey number linear in n; false already for maximum degree three.
Asks for the size Ramsey number of the balanced complete bipartite graph with n vertices on each side; known between orders n squared times two to the n and n cubed times two to the n.
Asks to prove the 1978 formula for the size Ramsey number of two star forests as a sum over diagonals of the largest star-size sums minus one; proved in special cases only.
Estimates the Ramsey number for r-uniform hypergraphs, the fewest vertices forcing a monochromatic complete r-uniform subhypergraph on n vertices.
Determines the least size m such that some two-coloring of the complete graph on n vertices leaves every vertex set of size at least m rich in both colors.
Estimates the Ramsey number for three-uniform hypergraphs, the fewest vertices forcing a monochromatic complete three-uniform subhypergraph on n vertices.
Bounds the induced Ramsey number, the fewest vertices of a host graph in which every two-coloring of the edges gives an induced monochromatic copy of a graph.
Asks whether a graph whose subgraphs on k at least 2 vertices have at most 2k-3 edges is Ramsey size linear; corrected from the site's wording, which no graph meets since one vertex exceeds the bound; open.
Asks whether the three-cube, the complete bipartite graph with three vertices per side, or the complete graph on four vertices with one edge subdivided is Ramsey size linear; open, with partial results.
Asks whether a graph with linear Ramsey numbers against trees and quadratic against complete graphs has Ramsey number linear in the edge count of every graph without isolated vertices.
Asks for the least constant c such that the Ramsey number of an odd cycle of length two k plus one against any m-edge graph without isolated vertices is at most c times m.
Asks whether, for each k at least three and sufficiently large m, the Ramsey number of a k-cycle against any m-edge graph without isolated vertices is at most two m plus the floor of half of (k minus one).
Every rational exponent in [1,2) is realized by the Turán number of a finite bipartite graph; records the 2026 proof, accepted on Lean built here, and its exposition qualifications.
Asks whether, for every k at least three, some graph on n vertices with no cycle of length two k has at least a constant times n to the power one plus one over k edges; known for k equal to 3 and 5, open for every other k.
Asks whether the most edges a graph on n vertices can have with no triangle and no four-cycle is asymptotic to n over two to the power three halves; the ratio is known only to lie between one and the square root of two.
Asks whether the most edges on n vertices avoiding cycles of length two k minus one and two k is asymptotic to n over two to the power one plus one over k, for k above one; disproved at k equal to 3 and 5.
Asks whether the extremal number of a finite family with a bipartite member is within a constant factor of some bipartite member's; false as written for two forests, and false for cyclic bipartite families by OpenAI's 2026 report.