PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
Ramsey's theorem (Theorem)

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

The standard proof proceeds by induction on $ k_1+k_2$. If $ k_1,k_2\leq 2$, 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$. Partition the rest of the vertices into two classes $ C_1$ and $ C_2$ according to whether edges from $ v$ are of color $ 1$ or $ 2$ respectively. By inductive hypothesis $ \left\lvert C_1\right\rvert $ is bounded since it contains no $ k_1-1$-clique of color $ 1$ and no $ k_2$-clique of color $ 2$. Similarly, $ \left\lvert C_2\right\rvert $ is bounded. QED.

Similar argument shows that for any positive integers $ k_1,k_2,\dotsc,k_t$ if we color the edges of a sufficiently large graph in $ t$ colors, then we would be able to find either $ k_1$-clique of color $ 1$, or $ k_2$-clique or color $ 2$,..., or $ k_t$-clique of color $ t$.

The minimum $ n$ whose existence stated in Ramsey's theorem is called Ramsey number and denoted by $ R(k_1,k_2)$ (and $ R(k_1,k_2,\dotsc,k_t)$ for multicolored graphs). The above proof shows that $ R(k_1,k_2)\leq R(k_1,k_2-1)+R(k_1-1,k_2)$. From that it is not hard to deduce by induction that $ R(k_1,k_2)\leq \binom{k_1+k_2-2}{k_1-1}$. In the most interesting case $ k_1=k_2=k$ this yields approximately $ R(k,k)\leq (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 $ 2^{1-k}$. Let $ I_r$ be the random variable which is $ 1$ if $ r$'th set of $ k$ elements is monochromatic clique and is 0 otherwise. The sum $ I_r$'s over all $ k$-element sets is simply the number of monochromatic $ k$-cliques. Therefore by linearity of expectation $ E(\sum I_r)=\sum E(I_r)=2^{1-k}\binom{n}{k}$. If the expectation is less than $ 1$, then there exists a coloring 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)\geq (\sqrt{2}+o(1))^{k}$.

The gap between the lower and upper bounds has been open for several decades. There have been a number of improvements in $ o(1)$ terms, but nothing better than $ \sqrt{2}+o(1)\leq R(k,k)^{1/k}\leq 4+o(1)$ is known. It is not even known whether $ \lim_{k\to \infty} R(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)\leq c_{k}x^{k-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 combination of results of Kim and improvement of Ajtai, Komlós and Szemerédi's result by Shearer [6] yields $ \tfrac{1}{162}(1+o(1)) k^2/\log k \leq R(3,k)\leq (1+o(1))k^2/\log k$.

A lot of machine and human time has been spent trying to determine Ramsey numbers for small $ k_1$ and $ k_2$. 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.
Zbl 0455.05045.
2
Noga Alon and Joel H. Spencer.
The probabilistic method.
John Wiley & Sons, Inc., second edition, 2000.
Zbl 0996.05001.
3
Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer.
Ramsey Theory.
Wiley-Interscience series in discrete mathematics. 1980.
Zbl 0455.05002.
4
Jeong Han Kim.
The Ramsey number $ R(3,t)$ has order of magnitude $ t^2/\log t$.
Random Structures & Algorithms, 7(3):173-207, 1995.
Zbl 0832.05084.
Preprint is available online.
5
Stanislaw Radziszowski.
Small Ramsey numbers.
Electronic Journal of Combinatorics, Dynamical Survey, 2002.
Available online.
6
James B. Shearer.
A note on the independence number of triangle-free graphs.
Discrete Mathematics, 46:83-87, 1983.
Zbl 0516.05053.
Abstract is available online



"Ramsey's theorem" is owned by bbukh.
(view preamble)

View style:

See Also: Ramsey's theorem, probabilistic method

Also defines:  Ramsey number
Log in to rate this entry.
(view current ratings)

Cross-references: Ramsey numbers, machine, fixed, upper bounds, Calculus, coloring, expectation, number, sum, random variable, lower bounds, QED, bounded, inductive hypothesis, cliques, contains, graph, induction, proof, colors, vertices, complete graph, edges, integers, positive
There is 1 reference to this entry.

This is version 15 of Ramsey's theorem, born on 2003-08-20, modified 2006-09-05.
Object id is 4630, canonical name is RamseysTheorem2.
Accessed 8119 times total.

Classification:
AMS MSC: 05D10 (Combinatorics :: Extremal combinatorics :: Ramsey theory)
 05D40 (Combinatorics :: Extremal combinatorics :: Probabilistic methods)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)