List of conjectures by Paul Erdős explained

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.

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

2 ^{n} contains at least one digit 2 for every n > 8 .

• The conjecture that the Erdős–Moser equation,, has no solutions except .

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.
• The Erdős sumset conjecture on sets, proven by Joel Moreira, Florian Karl Richter, Donald Robertson in 2018. The proof has appeared in "Annals of Mathematics" in March 2019.^[3]
• The Burr–Erdős conjecture on Ramsey numbers of graphs, proved by Choongbum Lee in 2015.
• 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.^[4]
• 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.^[5]
• The Erdős–Lovász conjecture on weak/strong delta-systems, proved by Michel Deza in 1974.^[6]
• 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.^[7]
• The Erdős–Graham conjecture in combinatorial number theory on monochromatic Egyptian fraction representations of unity, proved by Ernie Croot in 2000.^[8]
• The Erdős–Stewart conjecture on the Diophantine equation n! + 1 = p_k^a p_k+1^b, solved by Florian Luca in 2001.^[9]
• The Cameron–Erdős conjecture on sum-free sets of integers, proved by Ben Green and Alexander Sapozhenko in 2003–2004.^[10]
• The Erdős–Menger conjecture on disjoint paths in infinite graphs, proved by Ron Aharoni and Eli Berger in 2009.^[11]
• 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.^[12]
• The Erdős–Rankin conjecture on prime gaps, proved by Ford, Green, Konyagin, and Tao in 2014.
• The Erdős discrepancy problem on partial sums of ±1-sequences. Terence Tao announced a solution in September 2015; it was published in 2016.^[13]
• The Erdős squarefree conjecture that central binomial coefficients C(2n, n) are never squarefree for n > 4 was proved in 1996.
• The Erdős primitive set conjecture that the sum

\sum _{n\in} (1)/(n log n) for any primitive set A (a set where no member of the set divides another member) attains its maximum at the set of primes numbers, proved by Jared Duker Lichtman in 2022.^{[14] [15] [16]}

• The Erdős-Sauer problem about maximum number of edges an n-vertex graph can have without containing a k-regular subgraph, solved by Oliver Janzer and Benny Sudakov^{[17] [18]}

See also

• List of things named after Paul Erdős

External links

• Fan Chung, "Open problems of Paul Erdős in graph theory"
• Fan Chung, living version of "Open problems of Paul Erdős in graph theory"

Notes and References

1. .
2. .
3. .
4. .
5. .
6. .
7. .
8. . .
9. .
10. . .
11. .
12. .
13. The Erdős discrepancy problem. Terence. Tao. Terence Tao. 2016. 1509.05363. 10.19086/da.609. Discrete Analysis. 1–29. 3533300. 59361755 . 2397-3129.
14. Lichtman . Jared Duker . 2022-02-04 . A proof of the Erdős primitive set conjecture . math.NT . 2202.02384 .
15. Web site: Cepelewicz . Jordana . 2022-06-06 . Graduate Student's Side Project Proves Prime Number Conjecture . 2022-06-06 . Quanta Magazine . en.
16. Web site: Primes and Primitive Sets . Haran . Brady . . 2022-06-21 .
17. Janzer . Oliver . Sudakov . Benny . 2022-04-26 . Resolution of the Erdős-Sauer problem on regular subgraphs . math.CO . 2204.12455.
18. Web site: 2022-06-23 . New Proof Shows When Structure Must Emerge in Graphs . 2022-06-26 . Quanta Magazine . en.