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 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, Donald Robertson in 2018. The proof has appeared in "Annals of Mathematics" 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.[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 primes numbers, proved by Jared Duker Lichtman in 2022.[21][22][23]
- 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[24][25]
Erdős, P.; Hajnal, A. (1989), "Ramsey-type theorems", Combinatorics and complexity (Chicago, IL, 1987), Discrete Applied Mathematics, 25 (1–2): 37–52, doi:10.1016/0166-218X(89)90045-0, MR 1031262.
Moreira, J.; Richter, F. K.; Robertson, D. (2019), "A proof of a sumset conjecture of Erdős", Annals of Mathematics, 189 (2): 605–652, arXiv:1803.00498, doi:10.4007/annals.2019.189.2.4, MR 3919363, S2CID 119158401, Zbl 1407.05236.
Hajnal, A.; Szemerédi, E. (1970), "Proof of a conjecture of P. Erdős", Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, pp. 601–623, MR 0297607.
Sárközy, A. (1978), "On difference sets of sequences of integers. II", Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, 21: 45–53 (1979), MR 0536201.
Croot, Ernest S. III (2000), Unit Fractions, Ph.D. thesis, University of Georgia, Athens. Croot, Ernest S. III (2003), "On a coloring conjecture about unit fractions", Annals of Mathematics, 157 (2): 545–556, arXiv:math.NT/0311421, Bibcode:2003math.....11421C, doi:10.4007/annals.2003.157.545, S2CID 13514070.
Sapozhenko, A. A. (2003), "The Cameron-Erdős conjecture", Doklady Akademii Nauk, 393 (6): 749–752, MR 2088503. Green, Ben (2004), "The Cameron-Erdős conjecture", Bulletin of the London Mathematical Society, 36 (6): 769–778, arXiv:math.NT/0304058, doi:10.1112/S0024609304003650, MR 2083752, S2CID 119615076.
Ford, Kevin; Green, Ben; Konyagin, Sergei; Tao, Terence (2016), "Large gaps between consecutive prime numbers", Annals of Mathematics, Second series, 183 (3): 935–974, arXiv:1408.4505, doi:10.4007/annals.2016.183.3.4
Lichtman, Jared Duker (2022-02-04). "A proof of the Erdős primitive set conjecture". arXiv:2202.02384 [math.NT].
Janzer, Oliver; Sudakov, Benny (2022-04-26). "Resolution of the Erdős-Sauer problem on regular subgraphs". arXiv:2204.12455 [math.CO].