The original version of Ramsey’s theorem states that for every positive integers and there is such that if edges of a complete graph on vertices are colored in two colors, then there is either a -clique of the first color or -clique of the second color.
The standard proof proceeds by induction on . If , then the theorem holds trivially. To prove induction step we consider the graph that contains no cliques of the desired kind, and then consider any vertex of . Partition the rest of the vertices into two classes and according to whether edges from are of color or respectively. By inductive hypothesis is bounded since it contains no -clique of color and no -clique of color . Similarly, is bounded. QED.
Similar argument shows that for any positive integers if we color the edges of a sufficiently large graph in colors, then we would be able to find either -clique of color , or -clique or color ,…, or -clique of color .
The minimum whose existence stated in Ramsey’s theorem is called Ramsey number and denoted by (and for multicolored graphs). The above proof shows that . From that it is not hard to deduce by induction that . In the most interesting case this yields approximately . The lower bounds can be established by means of probabilistic construction as follows.
Take a complete graph on vertices and color its edges at random, choosing the color of each edge uniformly independently of all other edges. The probability that any given set of vertices is a monochromatic clique is . Let be the random variable which is if ’th set of elements is monochromatic clique and is otherwise. The sum ’s over all -element sets is simply the number of monochromatic -cliques. Therefore by linearity of expectation . If the expectation is less than , then there exists a coloring which has no monochromatic cliques. A little exercise in calculus shows that if we choose to be no more than then the expectation is indeed less than . Hence, .
The gap between the lower and upper bounds has been open (http://planetmath.org/Open3) for several decades. There have been a number of improvements in terms, but nothing better than is known. It is not even known whether exists.
The behavior of for fixed and large is equally mysterious. For this case Ajtai, Komlós and Szemerédi proved that . The matching lower bound has only recently been established for by Kim . Even in this case the asymptotics is unknown. The combination of results of Kim and improvement of Ajtai, Komlós and Szemerédi’s result by Shearer  yields .
- 1 Miklós Ajtai, János Komlós, and Endre Szemerédi. A note on Ramsey numbers. J. Combin. Theory Ser. A, 29(3):354–360, 1980. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0455.05045Zbl 0455.05045.
- 2 Noga Alon and Joel H. Spencer. The probabilistic method. John Wiley & Sons, Inc., second edition, 2000. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0996.05001Zbl 0996.05001.
- 3 Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey Theory. Wiley-Interscience series in discrete mathematics. 1980. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0455.05002Zbl 0455.05002.
- 4 Jeong Han Kim. The Ramsey number has order of magnitude . Random Structures & Algorithms, 7(3):173–207, 1995. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0832.05084Zbl 0832.05084. Preprint is http://research.microsoft.com/research/theory/jehkim/papers/ramsey5.pdfavailable online.
- 5 Stanislaw Radziszowski. Small Ramsey numbers. Electronic Journal of Combinatorics, Dynamical Survey, 2002. http://www.combinatorics.org/Surveys/ds1.pdfAvailable online.
- 6 James B. Shearer. A note on the independence number of triangle-free graphs. Discrete Mathematics, 46:83–87, 1983. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0516.05053Zbl 0516.05053. Abstract is http://www.research.ibm.com/people/s/shearer/abstracts/intfg.htmlavailable online
|Date of creation||2013-03-22 13:53:09|
|Last modified on||2013-03-22 13:53:09|
|Last modified by||bbukh (348)|