List of conjectures by Paul Erdős
From Wikipedia, the free encyclopedia
The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects, and in many cases Erdős offered monetary rewards for solving them.
The unsolved problems are commonly known as Erdős problems.
Unsolved
- The Erdős–Gyárfás conjecture on cycles with lengths equal to a power of two in graphs with minimum degree 3.
- The Erdős–Hajnal conjecture that in a family of graphs defined by an excluded induced subgraph, every graph has either a large clique or a large independent set.[1]
- The Erdős–Mollin–Walsh conjecture on consecutive triples of powerful numbers.
- The Erdős–Selfridge conjecture that a covering system with distinct moduli contains at least one even modulus.
- The Erdős–Straus conjecture on the Diophantine equation 4/n = 1/x + 1/y + 1/z.
- The Erdős conjecture on arithmetic progressions in sequences with divergent sums of reciprocals.
- The Erdős–Szekeres conjecture on the number of points needed to ensure that a point set contains a large convex polygon.
- The Erdős–Turán conjecture on additive bases of natural numbers.
- A conjecture on quickly growing integer sequences with rational reciprocal series.
- A conjecture with Norman Oler[2] on circle packing in an equilateral triangle with a number of circles one less than a triangular number.
- The minimum overlap problem to estimate the limit of M(n).
- A conjecture that the ternary expansion of contains at least one digit 2 for every .[3]
- The conjecture that the Erdős–Moser equation, 1k + 2k + ⋯ + (m − 1)k = mk, has no solutions except 11 + 21 = 31.
Solved
- The Erdős–Faber–Lovász conjecture on coloring unions of cliques, proved (for all large n) by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.[4]
- The Erdős sumset conjecture on sets, proven by Joel Moreira, Florian Karl Richter and Donald Robertson in 2018. The proof appeared in the Annals of Mathematics journal in March 2019.[5]
- The Burr–Erdős conjecture on Ramsey numbers of graphs, proved by Choongbum Lee in 2015.[6][7]
- A conjecture on equitable colorings proven in 1970 by András Hajnal and Endre Szemerédi and now known as the Hajnal–Szemerédi theorem.[8]
- A conjecture that would have strengthened the Furstenberg–Sárközy theorem to state that the number of elements in a square-difference-free set of positive integers could only exceed the square root of its largest value by a polylogarithmic factor, disproved by András Sárközy in 1978.[9]
- The Erdős–Lovász conjecture on weak/strong delta-systems, proved by Michel Deza in 1974.[10]
- The Erdős–Heilbronn conjecture in combinatorial number theory on the number of sums of two sets of residues modulo a prime, proved by Dias da Silva and Hamidoune in 1994.[11]
- The Erdős–Graham conjecture in combinatorial number theory on monochromatic Egyptian fraction representations of unity, proved by Ernie Croot in 2000.[12]
- The Erdős–Stewart conjecture on the Diophantine equation n! + 1 = pka pk+1b, solved by Florian Luca in 2001.[13]
- The Cameron–Erdős conjecture on sum-free sets of integers, proved by Ben Green and Alexander Sapozhenko in 2003–2004.[14]
- The Erdős–Menger conjecture on disjoint paths in infinite graphs, proved by Ron Aharoni and Eli Berger in 2009.[15]
- The Erdős distinct distances problem. The correct exponent was proved in 2010 by Larry Guth and Nets Katz, but the correct power of log n is still undetermined.[16]
- The Erdős–Rankin conjecture on prime gaps, proved by Ford, Green, Konyagin, and Tao in 2014.[17]
- The Erdős discrepancy problem on partial sums of ±1-sequences. Terence Tao announced a solution in September 2015; it was published in 2016.[18]
- The Erdős squarefree conjecture that central binomial coefficients C(2n, n) are never squarefree for n > 4 was proved in 1996 by Olivier Ramaré and Andrew Granville.[19][20]
- The Erdős primitive set conjecture that the sum for any primitive set A (a set where no member of the set divides another member) attains its maximum at the set of prime numbers, proved by Jared Duker Lichtman in 2022.[21][22][23]
- The Erdős–Sauer problem about the maximum number of edges an n-vertex graph can have without containing a k-regular subgraph, was solved by Oliver Janzer and Benny Sudakov.[24][25]
- Terence Tao reported that Erdős problem 728 was solved in 2026 using AI assistance.[26] The proof was constructed in the Lean proof language by Kevin Barreto and Liam Price with the assistance of ChatGPT 5.2 and the Aristotle Lean API.[27][28]
- Erdős problem 347 on the subset sums of sequences with ratio limit 2 was proved in January 2026 by Enrique Barschkis; the proof was formally verified in the Lean proof assistant.[29]
- In March 2026, Erdős problem 369 was solved by 17-year-old Sky Yang (Yueer Yang), and the result was later proven correct after verification in Lean.[30]
- Erdős problem 90, the planar unit distance problem, was solved by an internal OpenAI model.[31]
