List of conjectures by Paul Erdős
From Wikipedia, the free encyclopedia
(Redirected from Erdős conjecture (disambiguation))
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[edit]
- 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).
- Erdős discrepancy problem on partial sums of ±1-sequences.
- On September 2015, Terence Tao submitted a proof of this conjecture, which is currently under review
Solved[edit]
- 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]
- The Erdős–Lovász conjecture on weak/strong delta-systems, proved by Michel Deza in 1974.[3]
- 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.[4]
- The Erdős–Graham conjecture in combinatorial number theory on monochromatic Egyptian fraction representations of unity, proved by Ernie Croot in 2000.[5]
- The Erdős–Stewart conjecture on the Diophantine equation n! + 1 = pka pk+1b, solved by Luca in 2001.[6]
- The Cameron–Erdős conjecture on sum-free sets of integers, proved by Ben Green and Alexander Sapozhenko in 2003–2004.[7]
- The Erdős–Menger conjecture on disjoint paths in infinite graphs, proved by Ron Aharoni and Eli Berger in 2009.[8]
- 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.[9]
See also[edit]
References[edit]
- ^ 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.
- ^ 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.