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–Burr conjecture on Ramsey numbers of graphs.
- The Erdős–Faber–Lovász conjecture on coloring unions of cliques.
- 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 set contains at least one odd member.
- 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 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).
Solved
- 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.[2]
- 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.[3]
- The Erdős–Lovász conjecture on weak/strong delta-systems, proved by Michel Deza in 1974.[4]
- 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.[5]
- The Erdős–Graham conjecture in combinatorial number theory on monochromatic Egyptian fraction representations of unity, proved by Ernie Croot in 2000.[6]
- The Erdős–Stewart conjecture on the Diophantine equation n! + 1 = pka pk+1b, solved by Florian Luca in 2001.[7]
- The Cameron–Erdős conjecture on sum-free sets of integers, proved by Ben Green and Alexander Sapozhenko in 2003–2004.[8]
- The Erdős–Menger conjecture on disjoint paths in infinite graphs, proved by Ron Aharoni and Eli Berger in 2009.[9]
- 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 open.[10]
- Erdős discrepancy problem on partial sums of ±1-sequences.
See also
References
- ↑ Erdős, P.; Hajnal, A. (1989), "Ramsey-type theorems", Combinatorics and complexity (Chicago, IL, 1987), Discrete Appl. Math., 25 (1-2): 37–52, doi:10.1016/0166-218X(89)90045-0, MR 1031262.
- ↑ 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 536201.
- ↑ Deza, M. (1974), "Solution d'un problème de Erdős-Lovász", Journal of Combinatorial Theory, Series B (in French), 16: 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
, doi:10.4007/annals.2003.157.545. - ↑ Luca, Florian (2001), "On a conjecture of Erdős and Stewart", Mathematics of Computation, 70 (234): 893–896, 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.
- ↑ Aharoni, Ron; Berger, Eli (2009), "Menger's Theorem for infinite graphs", Inventiones Mathematicae, 176: 1–62, doi:10.1007/s00222-008-0157-3.
- ↑ Guth, l.; Katz, N. H. (2010), On the Erdős distinct distance problem on the plane, arXiv:1011.4105.
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"
This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.