Erdős–Graham conjecture

Erdős–Graham conjecture

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

:sum_{nin S}frac{1}{n} = 1.

In more detail, Paul Erdős and Ronald Graham conjectured that, for sufficiently large "r", the largest member of "S" could be bounded by "br" 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"167000. 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 6"r"; therefore, if the integers are "r"-colored there must be a monochromatic subset "C" satisfying the conditions of Croot's theorem.

See also

* Conjectures by Erdős

References

*cite paper
author = Croot, Ernest S., III
title = Unit Fractions
version = Ph.D. thesis
publisher = University of Georgia, Athens
date = 2000

* cite journal
author = Croot, Ernest S., III
year = 2003
title = On a coloring conjecture about unit fractions
journal = Annals of Mathematics
volume = 157
issue = 2
pages = 545–556
id = arxiv|archive = math.NT|id = 0311421

* cite journal
author = Erdős, Paul and Graham, Ronald L.
year = 1980
title = Old and new problems and results in combinatorial number theory
journal = L'Enseignement Mathématique
volume = 28
pages = 30–44

External links

* [http://www.math.gatech.edu/~ecroot/ Ernie Croot's Webpage]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Erdős–Graham problem — In combinatorial number theory, the Erdős–Graham problem is the problem of proving that, if the set {2, 3, 4, ...} of integers greater than one is partitioned into finitely many subsets, then one of the subsets can be used to form… …   Wikipedia

  • Erdős–Burr conjecture — Let G be a simple graph.It follows from Ramsey s theorem that there exists a least integer r(G), the Ramsey number of G , such that any complete graph on at least r(G) vertices whose edges are coloured red or blue contains a monochromatic copy of …   Wikipedia

  • Erdős conjecture — The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects.Some of these are the following: * The Cameron–Erdős conjecture on sum free sets of integers, solved by… …   Wikipedia

  • Conjecture d'Erdős-Burr — En théorie des graphes, la conjecture d Erdős Burr, proposée en 1973 par Paul Erdős et Stefan Burr (en) et toujours non résolue, concerne la croissance du nombre de Ramsey d un graphe non orienté de degré de dégénérescence donné, en fonction …   Wikipédia en Français

  • List of things named after Paul Erdős — The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… …   Wikipedia

  • Conjecture de Erdős-Burr — Conjecture d Erdős Burr Soit G un graphe simple. Il découle du théorème de Ramsey qu il existe un entier r(G) minimal, le nombre de Ramsey de G, tel que tout graphe complet d au moins r(G) sommets dont les arêtes sont coloriées en rouge et bleu… …   Wikipédia en Français

  • Erdős–Faber–Lovász conjecture — In graph theory, the Erdős–Faber–Lovász conjecture (1972) is a very deep problem about the coloring of graphs, named after Paul Erdős, Vance Faber, and László Lovász. It says::The union of k copies of k cliques intersecting in at most one vertex… …   Wikipedia

  • Erdos — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

  • Erdös — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

  • Paul Erdős — Paul Erdős, 1992 Paul Erdős (Erdős Pál /ˈɛrdøːʃ paːl …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”