Erdős–Graham conjecture

From Wikipedia, the free encyclopedia

The Erdős–Graham conjecture in combinatorial number theory states that, if {2,3,4,...} are partitioned into finitely many subsets, then one of the subsets can be used to form an Egyptian fraction representation of unity. That is, for every r > 0, and every r-coloring of the integers greater than one, there is a finite monochromatic subset S of these integers such that

In more detail, Paul Erdős and Ronald Graham conjectured that, for sufficiently large r, the largest member of S could be bounded by b^r for some constant b independent of r. It was known that, for this to be true, b must be at least e.

Ernie Croot proved the conjecture as part of his Ph.D thesis, and later (while a post-doctoral student at UC Berkeley) published the proof in the Annals of Mathematics. The value Croot gives for b is very large: it is at most e¹⁶⁷⁰⁰⁰. Croot's result follows as a corollary of a more general theorem stating the existence of Egyptian fraction representations of unity for sets C of smooth numbers in intervals of the form [X, X^1+δ], where C contains sufficiently many numbers so that the sum of their reciprocals is at least six. The Erdős–Graham conjecture follows from this result by showing that one can find an interval of this form in which the sum of the reciprocals of all smooth numbers is at least 6r; therefore, if the integers are r-colored there must be a monochromatic subset C satisfying the conditions of Croot's theorem.

[edit] See also

• Conjectures by Erdős

[edit] References

• 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. 

• Erdős, Paul and Graham, Ronald L. (1980). "Old and new problems and results in combinatorial number theory". L'Enseignement Mathématique 28: 30–44. 

[edit] External links

• Ernie Croot's Webpage