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 whether a family of sets closed under subsets always has an element contained in as many members as the largest intersecting subfamily has sets.
Asks whether, for k at least 4 and n large in terms of k, more k-subsets of the first n integers than those through a fixed pair force two meeting in one point; Frankl proved it, while the site's wording, with no range, fails.
The largest family of subsets of the first n integers in which no two members intersect in exactly r elements.
Estimates the chromatic number of the unit distance graph in n-dimensional space, whose edges join points at distance exactly one.
Asks whether some girth bound forces every finite unit distance graph in the plane to be 3-colorable.
Bounds the largest chromatic number of a graph on finitely many plane points whose edges join pairs at one of r prescribed distances.
Asks whether every finite Sidon set of integers can be extended to a perfect difference set modulo p squared plus p plus 1 for some prime p.
Bounds the fewest integers from a run of consecutive integers whose product is divisible by the product of n given integers; the corrected at-most statement is open, with a partial bound of 12n pending.
The least multiplier f(n) such that any f(n) max(A) consecutive integers hold distinct multiples of the n members of A, for every n-set A; known to lie between log n over log log n and root n, with a formula asked for.
Asks for an asymptotic formula for the shortest interval just above n with distinct integers, the kth divisible by k, for k up to n; known between n root log n over log log n and 1.74 n root log n, with a 2026 claim pending.
Bounds the shortest interval anywhere holding distinct integers, the kth divisible by k, for k up to n, against the one just above n; the comparison is proved (van Doorn 2026), the n to the 1+o(1) bound open, n^(3/2) proved.
Asks for the Turán density of the complete r-uniform hypergraph on k vertices for any k > r > 2; Turán's 1941 theorem settles r = 2 and no pair with r > 2 is known, with Erdős's two prize offers standing.
Asks whether every bipartite graph with at least two edges has extremal number asymptotic to a constant times a power of n in [1, 2), and whether that power is rational; Erdős's 1967 exponent shapes were disproved in 1970.
Asks whether the largest graph on n vertices with no complete bipartite subgraph with r vertices per side has roughly n to the power 2 minus one over r edges.
Asks whether every 4-regular graph contains a 3-regular subgraph, and whether some degree r forces one in every r-regular graph; both answered yes by Tashkinov in 1982, for degree 4 and for every degree at least 3.
Asks whether the largest 3-uniform hypergraph on n vertices containing no three edges spanning six vertices has o(n squared) edges, fewer than any fixed fraction of n squared for large n.
Asks whether the chromatic number of an n-vertex graph is at most a constant times n^{1/2}/log n times the order of its largest clique subdivision; the Erdős–Fajtlowicz conjecture, proved by Fox, Lee and Sudakov in 2013.
Asks whether a constant times r squared times n edges on n vertices always force a subdivision of the complete graph on r vertices; the conjecture of Erdős, Hajnal and Mader, proved by Bollobás–Thomason and Komlós–Szemerédi.
Asks whether every r-uniform hypergraph on n vertices is a union of at most ex_r(n; K_{r+1}^r) edges and (r+1)-cliques, no two sharing an edge; the Erdős–Sauer conjecture, known for r = 2.
Asks whether the size Ramsey number of the path grows faster than linearly but slower than quadratically, and whether that of the cycle is subquadratic; both are linear, so the first answer is no and the others yes.
Bounds the least n such that every red-blue coloring of 1 up to n has a red three-term progression or a blue k-term one; Green, Hunter and Schoen meet the two explicit challenges while the order of magnitude stays open.
Asks whether a Steiner system on n points with blocks of size k covering every r-set once exists for large n whenever the divisibility conditions hold.
Asks whether the order of a finite projective plane must always be a power of a prime.
Asks whether the largest number of mutually orthogonal Latin squares of order n grows at least as fast as a constant times the square root of n.
Asks for an asymptotic formula for the number of Latin rectangles with k rows and n columns.