Ramsey’s theorem


The original version of Ramsey’s theorem states that for every positive integers k1 and k2 there is n such that if edges of a complete graphMathworldPlanetmath on n vertices are colored in two colors, then there is either a k1-clique of the first color or k2-clique of the second color.

The standard proof proceeds by inductionMathworldPlanetmath on k1+k2. If k1,k22, then the theorem holds trivially. To prove induction step we consider the graph G that contains no cliques of the desired kind, and then consider any vertex v of G. PartitionMathworldPlanetmathPlanetmath the rest of the vertices into two classes C1 and C2 according to whether edges from v are of color 1 or 2 respectively. By inductive hypothesis |C1| is bounded since it contains no k1-1-clique of color 1 and no k2-clique of color 2. Similarly, |C2| is bounded. QED.

Similar argument shows that for any positive integers k1,k2,,kt if we color the edges of a sufficiently large graph in t colors, then we would be able to find either k1-clique of color 1, or k2-clique or color 2,…, or kt-clique of color t.

The minimum n whose existence stated in Ramsey’s theorem is called Ramsey numberMathworldPlanetmath and denoted by R(k1,k2) (and R(k1,k2,,kt) for multicolored graphs). The above proof shows that R(k1,k2)R(k1,k2-1)+R(k1-1,k2). From that it is not hard to deduce by induction that R(k1,k2)(k1+k2-2k1-1). In the most interesting case k1=k2=k this yields approximately R(k,k)(4+o(1))k. The lower bounds can be established by means of probabilistic construction as follows.

Take a complete graph on n 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 k vertices is a monochromatic clique is 21-k. Let Ir be the random variableMathworldPlanetmath which is 1 if r’th set of k elements is monochromatic clique and is 0 otherwise. The sum Ir’s over all k-element sets is simply the number of monochromatic k-cliques. Therefore by linearity of expectation E(Ir)=E(Ir)=21-k(nk). If the expectation is less than 1, then there exists a coloringMathworldPlanetmath which has no monochromatic cliques. A little exercise in calculus shows that if we choose n to be no more than (2+o(1))k/2 then the expectation is indeed less than 1. Hence, R(k,k)(2+o(1))k.

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 o(1) terms, but nothing better than 2+o(1)R(k,k)1/k4+o(1) is known. It is not even known whether limkR(k,k)1/k exists.

The behavior of R(k,x) for fixed k and large x is equally mysterious. For this case Ajtai, Komlós and Szemerédi[1] proved that R(k,x)ckxk-1/(ln)k-2. The matching lower bound has only recently been established for k=3 by Kim [4]. Even in this case the asymptotics is unknown. The combinationMathworldPlanetmathPlanetmath of results of Kim and improvement of Ajtai, Komlós and Szemerédi’s result by Shearer [6] yields 1162(1+o(1))k2/logkR(3,k)(1+o(1))k2/logk.

A lot of machine and human time has been spent trying to determine Ramsey numbers for small k1 and k2. An up-to-date summary of our knowledge about small Ramsey numbers can be found in [5].

References

  • 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 R(3,t) has order of magnitude t2/logt. Random StructuresMathworldPlanetmath & 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 numberMathworldPlanetmath 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
Title Ramsey’s theorem
Canonical name RamseysTheorem
Date of creation 2013-03-22 13:53:09
Last modified on 2013-03-22 13:53:09
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 18
Author bbukh (348)
Entry type Theorem
Classification msc 05D40
Classification msc 05D10
Related topic RamseysTheorem
Related topic ProbabilisticMethod
Defines Ramsey number