List of conjectures by Paul Erdős

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$ .^[3]
The conjecture that the Erdős–Moser equation, $1 k + 2 k + \dots + (m - 1) k = m k$ , has no solutions except $11 + 2 1 = 3 1$ .

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, 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 = p_k^a p_k+1^b, 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 $\sum _{n\in A}{\frac {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.^[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]

References

^ 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.
^ Oler, Norman (1961), "A finite packing problem", Canadian Mathematical Bulletin, 4 (2): 153–155, doi:10.4153/CMB-1961-018-7, MR 0133065.
^ Lagarias, Jeffrey C. (2009), "Ternary expansions of powers of 2", Journal of the London Mathematical Society, Second Series, 79 (3): 562–588, arXiv:math/0512006, doi:10.1112/jlms/jdn080, MR 2506687, S2CID 15615918
^ Houston-Edwards, Kelsey (5 April 2021), "Mathematicians Settle Erdős Coloring Conjecture", Quanta Magazine, retrieved 2021-04-05
^ 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.
^ Kalai, Gil (May 22, 2015), "Choongbum Lee proved the Burr-Erdős conjecture", Combinatorics and more, retrieved 2015-05-22
^ Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics, 185 (3): 791–829, arXiv:1505.04773, doi:10.4007/annals.2017.185.3.2, S2CID 7974973
^ 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.
^ Deza, M. (1974), "Solution d'un problème de Erdős-Lovász", Journal of Combinatorial Theory, Series B (in French), 16 (2): 166–167, doi:10.1016/0095-8956(74)90059-8, MR 0337635.
^ da Silva, Dias; A., J.; Hamidoune, Y. O. (1994), "Cyclic spaces for Grassmann derivatives and additive theory", Bulletin of the London Mathematical Society, 26 (2): 140–146, doi:10.1112/blms/26.2.140.
^ 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.
^ Luca, Florian (2001), "On a conjecture of Erdős and Stewart", Mathematics of Computation, 70 (234): 893–896, Bibcode:2001MaCom..70..893L, doi:10.1090/S0025-5718-00-01178-9, MR 1677411.
^ 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.
^ Aharoni, Ron; Berger, Eli (2009), "Menger's Theorem for infinite graphs", Inventiones Mathematicae, 176 (1): 1–62, arXiv:math/0509397, Bibcode:2009InMat.176....1A, doi:10.1007/s00222-008-0157-3, S2CID 15355399.
^ Guth, Larry; Katz, Nets H. (2015), "On the Erdős distinct distances problem in the plane", Annals of Mathematics, Second series, 181 (1): 155–190, arXiv:1011.4105, doi:10.4007/annals.2015.181.1.2.
^ 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
^ Tao, Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363. doi:10.19086/da.609. ISSN 2397-3129. MR 3533300. S2CID 59361755.
^ Sárközy, A. (1985), "On divisors of binomial coefficients. I", Journal of Number Theory, 20 (1): 70–80, doi:10.1016/0022-314X(85)90017-4, MR 0777971
^ Ramaré, Olivier; Granville, Andrew (1996), "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients", Mathematika, 43 (1): 73–107, doi:10.1112/S0025579300011608
^ Lichtman, Jared Duker (2022-02-04). "A proof of the Erdős primitive set conjecture". arXiv:2202.02384 [math.NT].
^ Cepelewicz, Jordana (2022-06-06). "Graduate Student's Side Project Proves Prime Number Conjecture". Quanta Magazine. Retrieved 2022-06-06.
^ Haran, Brady. "Primes and Primitive Sets". Numberphile. Retrieved 2022-06-21.
^ Janzer, Oliver; Sudakov, Benny (2022-04-26). "Resolution of the Erdős-Sauer problem on regular subgraphs". arXiv:2204.12455 [math.CO].
^ "New Proof Shows When Structure Must Emerge in Graphs". Quanta Magazine. 2022-06-23. Retrieved 2022-06-26.

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"
"Erdős Problems". Erdős Problems. Retrieved 31 October 2024.

[1] 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.

[2] Oler, Norman (1961), "A finite packing problem", Canadian Mathematical Bulletin, 4 (2): 153–155, doi:10.4153/CMB-1961-018-7, MR 0133065.

[3] Lagarias, Jeffrey C. (2009), "Ternary expansions of powers of 2", Journal of the London Mathematical Society, Second Series, 79 (3): 562–588, arXiv:math/0512006, doi:10.1112/jlms/jdn080, MR 2506687, S2CID 15615918

[4] Houston-Edwards, Kelsey (5 April 2021), "Mathematicians Settle Erdős Coloring Conjecture", Quanta Magazine, retrieved 2021-04-05

[5] 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.

[6] Kalai, Gil (May 22, 2015), "Choongbum Lee proved the Burr-Erdős conjecture", Combinatorics and more, retrieved 2015-05-22

[7] Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics, 185 (3): 791–829, arXiv:1505.04773, doi:10.4007/annals.2017.185.3.2, S2CID 7974973

[8] 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.

[9] 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.

[10] Deza, M. (1974), "Solution d'un problème de Erdős-Lovász", Journal of Combinatorial Theory, Series B (in French), 16 (2): 166–167, doi:10.1016/0095-8956(74)90059-8, MR 0337635.

[11] Silva, Dias; A., J.; Hamidoune, Y. O. (1994), "Cyclic spaces for Grassmann derivatives and additive theory", Bulletin of the London Mathematical Society, 26 (2): 140–146, doi:10.1112/blms/26.2.140.

[12] 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.

[13] Luca, Florian (2001), "On a conjecture of Erdős and Stewart", Mathematics of Computation, 70 (234): 893–896, Bibcode:2001MaCom..70..893L, doi:10.1090/S0025-5718-00-01178-9, MR 1677411.

[14] 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.

[15] Aharoni, Ron; Berger, Eli (2009), "Menger's Theorem for infinite graphs", Inventiones Mathematicae, 176 (1): 1–62, arXiv:math/0509397, Bibcode:2009InMat.176....1A, doi:10.1007/s00222-008-0157-3, S2CID 15355399.

[16] Guth, Larry; Katz, Nets H. (2015), "On the Erdős distinct distances problem in the plane", Annals of Mathematics, Second series, 181 (1): 155–190, arXiv:1011.4105, doi:10.4007/annals.2015.181.1.2.

[17] 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

[18] Tao, Terence (2016). "The Erdős discrepancy problem". Discrete Analysis: 1–29. arXiv:1509.05363. doi:10.19086/da.609. ISSN 2397-3129. MR 3533300. S2CID 59361755.

[19] Sárközy, A. (1985), "On divisors of binomial coefficients. I", Journal of Number Theory, 20 (1): 70–80, doi:10.1016/0022-314X(85)90017-4, MR 0777971

[20] Ramaré, Olivier; Granville, Andrew (1996), "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients", Mathematika, 43 (1): 73–107, doi:10.1112/S0025579300011608

[21] Lichtman, Jared Duker (2022-02-04). "A proof of the Erdős primitive set conjecture". arXiv:2202.02384 [math.NT].

[22] Cepelewicz, Jordana (2022-06-06). "Graduate Student's Side Project Proves Prime Number Conjecture". Quanta Magazine. Retrieved 2022-06-06.

[23] Haran, Brady. "Primes and Primitive Sets". Numberphile. Retrieved 2022-06-21.

[24] Janzer, Oliver; Sudakov, Benny (2022-04-26). "Resolution of the Erdős-Sauer problem on regular subgraphs". arXiv:2204.12455 [math.CO].

[25] "New Proof Shows When Structure Must Emerge in Graphs". Quanta Magazine. 2022-06-23. Retrieved 2022-06-26.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Unsolved

Solved

See also

References

External links