Ramsey's theorem

Theorem

Ramsey's theorem

T-109Home MU-307Threads structure · number

Statement

Let \(r,s \in \mathbb{N}\) with \(r,s \geq 2\). Colour the edges of the complete graph \(K_n\) (on \(n\) labelled vertices, every pair joined by exactly one edge) using two colours, red and blue. Then there exists a least positive integer \(R(r,s)\), called the Ramsey number of \((r,s)\), with the property that for every \(n \geq R(r,s)\) and every red/blue colouring of the edges of \(K_n\), there is either a set of \(r\) vertices all of whose \(\binom{r}{2}\) joining edges are red (a red \(K_r\)), or a set of \(s\) vertices all of whose \(\binom{s}{2}\) joining edges are blue (a blue \(K_s\)). In particular \(R(r,s)\) is finite for every choice of \(r,s\).

Why it matters

Ramsey's theorem is the founding result of Ramsey theory: it asserts that total disorder — a colouring with no large monochromatic substructure — is impossible once the ambient structure is big enough. However you try to 2-colour the edges of a sufficiently large complete graph, some prescribed amount of order is forced upon you; you cannot design your way around it. This flips the usual combinatorial question ("can I build an example avoiding property \(P\)?") into an existence guarantee that holds for every colouring, adversarial or not.

The theorem is the prototype for an entire family of results (Ramsey theory for hypergraphs, Schur's theorem, van der Waerden's theorem on arithmetic progressions, the Hales–Jewett theorem) all of which share the same shape: sufficiently large + finitely coloured \(\Rightarrow\) monochromatic structured substructure. It is also a key early example of the probabilistic method's lower-bound counterpart, and it underlies applications from communication complexity to model theory.

Hypotheses

Two colours only (each edge gets exactly one of red/blue).With three or more colours the same qualitative statement is true (a multicolour Ramsey theorem also holds, by the identical inductive argument with more cases), but the specific bound proved below is for two colours; conflating the two-colour recursion with a \(k\)-colour count gives the wrong numerical bound. Complete graph as host: every pair of vertices is joined by an edge.If some pairs are simply absent (the host graph is not complete), a red/blue colouring of the present edges need never contain a monochromatic \(K_r\) or \(K_s\): colour a graph with no edges at all — trivially every "colouring" avoids both, for any \(r,s \geq 3\), since there are no edges to force a triangle or any complete subgraph. Finitely many vertices are enough — but \(n\) must be taken large (\(n \geq R(r,s)\)).For \(n \lt R(r,s)\) the guarantee fails by definition of \(R(r,s)\) as the least threshold: e.g. \(R(3,3)=6\), and there is an explicit red/blue colouring of \(K_5\) (the red edges forming a 5-cycle, blue the complementary 5-cycle) with no monochromatic triangle, so the conclusion genuinely needs \(n\geq 6\). \(r,s \geq 2\) (degenerate colours excluded).The convention \(R(r,1)=1\) is usually adopted (a single vertex trivially contains a blue \(K_1\)) but is a degenerate boundary case; the substantial content and the inductive proof both require \(r,s\geq 2\), where \(R(2,s)=s\) and \(R(r,2)=r\) already need checking as base cases.

Proof

We prove the two-colour graph Ramsey theorem by induction on \(r+s\), establishing along the way the explicit finite bound \(R(r,s) \leq \binom{r+s-2}{r-1}\).

Base cases: \(R(r,2)=r\) and \(R(2,s)=s\) for all \(r,s\geq 2\).

If every edge of \(K_r\) is red, we have a red \(K_r\) outright; if at least one edge is blue, its two endpoints form a blue \(K_2\). So \(n=r\) suffices, giving \(R(r,2)\leq r\); and \(K_{r-1}\) coloured entirely red has no blue \(K_2\) (no blue edge) and no red \(K_r\) (only \(r-1\) vertices), so \(R(r,2)\gt r-1\). Hence \(R(r,2)=r\) exactly; symmetrically \(R(2,s)=s\). A

Inductive hypothesis: for some \(r,s\geq 3\), assume \(R(r-1,s)\) and \(R(r,s-1)\) both exist (are finite).

Strong induction on \(r+s\): the base level \(r+s=4\) is covered by Step 1 (there \(\min(r,s)=2\)); we now show existence for general \(r,s\geq 3\) assuming it for all pairs with smaller sum. A

Key recursive bound: \(R(r,s) \leq R(r-1,s) + R(r,s-1)\).

This is the heart of the argument, proved in the next two steps. B

Set \(N = R(r-1,s)+R(r,s-1)\) and take any red/blue colouring of \(K_N\). Fix a vertex \(v\). Partition the remaining \(N-1\) vertices into \(A=\{\)neighbours joined to \(v\) by a red edge\(\}\) and \(B=\{\)neighbours joined to \(v\) by a blue edge\(\}\).

Every edge is red or blue by hypothesis (total 2-colouring), so \(A\) and \(B\) partition the other \(N-1\) vertices: \(|A|+|B|=N-1\). This uses only that the colouring is a function from edges to \(\{\text{red},\text{blue}\}\). A

Pigeonhole: \(|A| \geq R(r-1,s)\) or \(|B|\geq R(r,s-1)\).

If both failed, \(|A|\leq R(r-1,s)-1\) and \(|B|\leq R(r,s-1)-1\), so \(|A|+|B| \leq N-2\), contradicting \(|A|+|B|=N-1\) from Step 4. This is the pigeonhole principle applied to the two-part partition. B

Case \(|A|\geq R(r-1,s)\): the induced colouring on \(A\) (a complete graph on \(|A|\geq R(r-1,s)\) vertices, since \(A\) is a vertex subset of the complete graph \(K_N\)) contains a red \(K_{r-1}\) or a blue \(K_s\), by the inductive hypothesis of Step 2.

Applying the definition of \(R(r-1,s)\) to the sub-colouring restricted to \(A\); restriction of a colouring of \(K_N\) to a vertex subset is again a total red/blue colouring of the (complete) induced subgraph on that subset, so the inductive hypothesis applies verbatim. B

In the sub-case of Step 6: if \(A\) contains a blue \(K_s\), we are done (found in \(K_N\)). If instead \(A\) contains a red \(K_{r-1}\), say on vertex set \(S\), then \(S\cup\{v\}\) is a red \(K_r\): every vertex of \(S\) is joined to \(v\) by a red edge because \(S\subseteq A\) by construction of \(A\) in Step 4, and all edges within \(S\) are red by choice of \(S\).

Direct verification that \(S\cup\{v\}\) has all \(\binom{r}{2}\) edges red: edges inside \(S\) are red by the choice of \(S\); edges from \(v\) to \(S\) are red since \(S \subseteq A\) and \(A\) was defined as vertices joined to \(v\) in red. A

Case \(|B|\geq R(r,s-1)\): symmetrically, \(B\) contains a red \(K_r\) (done) or a blue \(K_{s-1}\) on some set \(T\), in which case \(T\cup\{v\}\) is a blue \(K_s\), since \(T\subseteq B\) means every edge from \(v\) to \(T\) is blue.

Mirror image of Steps 6–7, swapping the roles of red/\(r\) and blue/\(s\), \(A\) and \(B\). A

In every case (Steps 5–8) \(K_N\) contains a red \(K_r\) or a blue \(K_s\); since the colouring of \(K_N\) was arbitrary, this proves \(R(r,s)\leq N = R(r-1,s)+R(r,s-1)\), establishing Step 3, and in particular \(R(r,s)\) is finite because \(R(r-1,s)\) and \(R(r,s-1)\) are finite by the inductive hypothesis.

Collecting the exhaustive case split of Steps 5–8: every possible outcome of the pigeonhole dichotomy yields the required monochromatic clique, so no colouring of \(K_N\) can avoid both. This closes the induction on \(r+s\), so by strong induction \(R(r,s)\) exists (is a finite positive integer) for all \(r,s\geq 2\). B

\[R(r,s) \leq \binom{r+s-2}{r-1}.\]

By induction on \(r+s\) using Step 3 and the Pascal's-rule identity \(\binom{r+s-3}{r-2}+\binom{r+s-3}{r-1}=\binom{r+s-2}{r-1}\): assuming \(R(r-1,s)\leq\binom{r+s-3}{r-2}\) and \(R(r,s-1)\leq\binom{r+s-3}{r-1}\) (inductive hypothesis, same induction as Step 2), Step 3 gives \(R(r,s)\leq \binom{r+s-3}{r-2}+\binom{r+s-3}{r-1}=\binom{r+s-2}{r-1}\). The base cases \(R(r,2)=r=\binom{r}{1}\) and \(R(2,s)=s=\binom{s}{1}\) match the formula, anchoring the induction. C

Result

\forall r,s \geq 2,\ \exists\, R(r,s) \in \mathbb{N} \text{ such that every red/blue colouring of } K_{R(r,s)} \text{ contains a red } K_r \text{ or a blue } K_s.

Reading. No matter how adversarially you 2-colour the edges of a large enough complete graph, you cannot avoid producing a large monochromatic clique of one colour or the other — and "large enough" is a fixed finite number depending only on the two clique sizes you're trying to force, not on any property of the particular colouring.

Scope. Applies to finite complete graphs with a 2-edge-colouring. Extends verbatim (by the identical case-split argument, more colours in Step 5's pigeonhole split) to any fixed finite number of colours, and to \(k\)-uniform hypergraphs in place of graphs (edges = \(k\)-subsets rather than pairs) via the analogous but heavier induction; also extends to an infinite version (Infinite Ramsey theorem, for colourings of \(\mathbb{N}^{(2)}\)) by a different, non-quantitative compactness-style argument. Does not by itself give good bounds — the bound of Step 10 is exponential and known to be far from tight for the diagonal case \(R(r,r)\).

Corollaries & converses

Party corollary. \(R(3,3)=6\): among any 6 people, there are 3 mutual acquaintances or 3 mutual strangers (colour "knows" red, "doesn't know" blue); this is sharp, since the 5-cycle colouring of \(K_5\) exhibits 5 people with neither.
Symmetry. \(R(r,s)=R(s,r)\) for free, by relabelling red \(\leftrightarrow\) blue throughout the argument.
Monotonicity. \(R(r,s)\) is non-decreasing in each argument: a colouring of \(K_n\) avoiding a red \(K_r\) and blue \(K_s\) restricts to one avoiding red \(K_{r'}\) and blue \(K_s\) for any \(r' \leq r\), on the same \(n\), so \(R(r',s) \leq R(r,s)\).
Converse. The theorem is an existence/threshold statement, not an "if and only if" biconditional, so there is no converse to prove false in the usual sense; what can fail is the sharpness of a claimed value — asserting \(R(r,s)=N\) requires exhibiting both a colouring of \(K_{N-1}\) with no monochromatic clique of the right size (this the theorem itself does not supply) and the upper bound \(R(r,s)\leq N\) (which the theorem does supply, non-sharply, via Step 10). Exact values of \(R(r,s)\) are known only for very small \(r,s\); e.g. \(R(4,4)=18\) is known but \(R(5,5)\) is not, only bracketed between 43 and 48.

Fails without

Drop "complete host graph": colour the empty graph on any number of vertices (no edges at all, so vacuously "properly" red/blue coloured) — it contains no monochromatic \(K_r\) for any \(r\geq 2\), however many vertices you take, because there are no edges to be red or blue in the first place.
Drop "\(n\) large enough" (i.e. take \(n \lt R(r,s)\)): for \(r=s=3\), take \(n=5\) and colour the edges of \(K_5\) by a red 5-cycle and its complementary blue 5-cycle (the "pentagon/pentagram" colouring). Direct check: every vertex has exactly 2 red and 2 blue edges, and no three vertices are pairwise joined by edges of a single colour, so this colouring of \(K_5\) contains neither a red nor a blue triangle — showing \(R(3,3) \gt 5\), i.e. the conclusion genuinely fails at \(n=5\).
Drop "finitely many colours" (allow a colouring by an infinite palette with no repetition forced): colouring each edge of \(K_n\) a distinct colour trivially has no monochromatic \(K_r\) for \(r\geq 3\) at any finite \(n\), for exactly the reason the pigeonhole step (Step 5) needs finitely many colour-classes to force one of them to be large.

Common errors

Believing \(R(r,s)=r\cdot s\) or some other simple closed form; only a handful of exact Ramsey numbers are known, and the true growth rate of \(R(r,r)\) is not pinned down even up to matching constants in the exponent (best known bounds are exponential with distinct bases, an open problem since Erdős–Szekeres 1935).
Applying the recursive bound \(R(r,s)\leq R(r-1,s)+R(r,s-1)\) as though it were an equality; it is generally strict (e.g. it gives \(R(3,3)\leq R(2,3)+R(3,2)=3+3=6\), which happens to be tight, but for larger \(r,s\) the bound of Step 10 is known to overshoot the truth substantially).
Forgetting that the vertex \(v\) singled out in Step 4 must be excluded from \(A\) and \(B\) and then correctly re-attached in Steps 7–8; omitting the "\(\cup\{v\}\)" step is a common gap that leaves only a clique of size \(r-1\) or \(s-1\), not \(r\) or \(s\).
Confusing the graph Ramsey number \(R(r,s)\) (edges 2-coloured) with the hypergraph or multicolour Ramsey numbers, which exist by the same style of argument but have different (typically much larger) values.
Treating the sharp lower-bound colouring for one \((r,s)\) (e.g. the pentagon colouring for \((3,3)\)) as a general recipe; extremal colourings for larger Ramsey numbers are not simple cyclic patterns and in most cases are not explicitly known at all, only shown to exist via the probabilistic method.

Discussion

Ramsey's theorem was proved by Frank P. Ramsey in 1930, in a paper ("On a Problem of Formal Logic") whose actual motivation was a decision problem for first-order logic, not combinatorics for its own sake — the now-famous graph-theoretic statement was essentially a lemma. The finite party-problem formulation and small numerical values were popularised later, notably by Erdős and Szekeres (1935), who independently rediscovered the finite version and proved the exponential-type upper bound of Step 10 by exactly this induction.

The gap between the upper bound of Step 10 (roughly \(4^r\) for the diagonal case \(R(r,r)\)) and the best known lower bound (roughly \(\sqrt{2}^{\,r}\), from Erdős's 1947 probabilistic argument: a uniformly random 2-colouring of \(K_n\) has, in expectation, few monochromatic \(K_r\)'s when \(n\) is below that threshold, so some colouring must avoid them entirely) remains open; closing it — even determining the base of the exponential growth — is one of the best-known open problems in combinatorics.

The proof strategy generalises far beyond graphs: the same "fix a point, pigeonhole its links, induct" template proves Ramsey's theorem for \(k\)-uniform hypergraphs and for any fixed finite number of colours, and a genuinely different, non-constructive compactness argument (using König's lemma or an ultrafilter/ compactness-of-product-space argument) extends it to the infinite Ramsey theorem: any 2-colouring of the edges of the complete graph on \(\mathbb{N}\) contains an infinite monochromatic clique. The infinite theorem in fact implies the finite one (by a compactness argument extracting a uniform finite bound from the infinite statement), giving an alternative, non-elementary proof route.

Common misconception: many students read "complete disorder is impossible" as saying large random-looking colourings are somehow rare or unlikely; in fact the theorem says the opposite of a probabilistic near-miss — it holds for every single colouring, including deliberately adversarial ones, and gives no information about how many monochromatic cliques appear, only that at least one must.

Worked examples

Show directly that \(R(3,3) \leq 6\): any red/blue colouring of \(K_6\) contains a monochromatic triangle.

Instance of the general proof (Steps 4–9) specialised to \(r=s=3\); redo it concretely to see the mechanism. A

Fix any vertex \(v\) of \(K_6\); it has 5 incident edges, each red or blue.

\(K_6\) is complete, so \(v\) is joined to all other 5 vertices; total 2-colouring means each such edge is red or blue. A

By pigeonhole, at least \(\lceil 5/2 \rceil = 3\) of these 5 edges share a colour; say (WLOG, by red/blue symmetry) at least 3 are red, going to vertices \(a,b,c\).

Pigeonhole principle: 5 objects into 2 classes forces a class of size \(\geq 3\); this is Step 5 of the general proof specialised (here \(R(2,3)=R(3,2)=3\) plays the role of the threshold on each side). B

Consider the 3 edges among \(\{a,b,c\}\). If any one of them is red, say \(ab\), then \(\{v,a,b\}\) is a red triangle. If none is red, all three of \(ab,bc,ca\) are blue, giving a blue triangle \(\{a,b,c\}\).

Exhaustive case split on the colour of edges within \(\{a,b,c\}\) — mirrors Step 7 of the general proof, with \(S\) a single edge (a red \(K_2\), since \(R(2,3)-1=1\) is the relevant sub-threshold) rather than a bigger clique. B

R(3,3) \leq 6

Reading. Among any 6 people, there are always 3 mutual acquaintances or 3 mutual strangers.

Using \(R(3,3)=6\) (established above, sharp by the pentagon colouring of \(K_5\)) and the recursive bound of Step 3, obtain an explicit upper bound for \(R(3,4)\).

Apply Step 3 with \(r=3,s=4\): \(R(3,4)\leq R(2,4)+R(3,3)\). A

By the base case of Step 1, \(R(2,4)=4\).

General base case \(R(2,s)=s\), instantiated at \(s=4\). A

Hence \(R(3,4) \leq 4+6=10\).

Substitute Step 2 and the known value \(R(3,3)=6\) into the inequality of Step 1. A

(For context, not reproved here.) The true value is \(R(3,4)=9\), strictly below our bound of 10, obtained by an explicit 8-vertex colouring with neither a red triangle nor a blue \(K_4\), plus a sharper case analysis than the generic recursion.

Cited as a known exact value (Greenwood–Gleason, 1955) to illustrate that the recursive bound of Step 3, while always valid, is not always tight; not re-derived here since it needs a bespoke combinatorial argument beyond the scope of the general theorem's proof. C

R(3,4) \leq 10 \quad(\text{true value: } R(3,4)=9)

Reading. This shows how the induction that proves the theorem also machine-generates concrete numerical bounds, and how those generic bounds can be loose compared to the true (much harder to compute) Ramsey number.

Problems

Show using only the base cases of Step 1 and the recursion of Step 3 that \(R(4,2)=4\) and \(R(2,5)=5\), and explain why no computation is needed beyond quoting the base case directly.
Solution
These are literally the base cases of Step 1 with \(r=4\) (giving \(R(4,2)=4\)) and \(s=5\) (giving \(R(2,5)=5\)); no recursive step is needed since one of the two parameters already equals 2, which is exactly the regime the base case covers. Concretely for \(R(4,2)=4\): colouring \(K_4\) entirely red gives a red \(K_4\) trivially, and colouring \(K_3\) entirely red has no blue edge and only 3 vertices so no red \(K_4\), showing \(R(4,2) \gt 3\); combined, \(R(4,2)=4\).
Using the recursive bound of Step 3 and the values \(R(3,3)=6\), \(R(2,4)=4\), \(R(2,5)=5\), \(R(3,4)\leq 10\) (from Worked Example 2), derive an upper bound for \(R(4,4)\) (you will need \(R(3,4)\) twice).
Solution
Step 3 gives \(R(4,4)\leq R(3,4)+R(4,3)\). By the symmetry corollary, \(R(4,3)=R(3,4)\leq 10\). So \(R(4,4)\leq 10+10=20\). (The true value, proved by finer methods, is \(R(4,4)=18\); this shows the generic bound overshoots by only 2 in this case — much tighter than the diagonal bound tends to be for larger \(r\).)
A red/blue colouring of \(K_5\) is given by colouring edge \(\{i,j\}\) (vertices labelled \(0,1,2,3,4\)) red if \(|i-j| \bmod 5 \in \{1,4\}\) and blue if \(|i-j|\bmod 5 \in \{2,3\}\). Verify this has no monochromatic triangle, and explain precisely which hypothesis of the theorem this exhibits as necessary.
Solution
This is the "pentagon/pentagram" colouring: red edges form the 5-cycle \(0\text{-}1\text{-}2\text{-}3\text{-}4\text{-}0\), blue edges form the complementary 5-cycle \(0\text{-}2\text{-}4\text{-}1\text{-}3\text{-}0\). Checking all \(\binom{5}{3}=10\) triples: each triple of vertices in a 5-cycle spans at most 2 cycle-edges (since 3 vertices out of a 5-cycle cannot all be mutually adjacent in that cycle — the cycle has girth 5), so no triple is monochromatic red (needs all 3 pairs to be cycle-edges of the red 5-cycle) nor monochromatic blue by the same argument on the blue 5-cycle. This exhibits the necessity of the hypothesis "\(n\) large enough (\(n\geq R(r,s)\))" from the Hypotheses section: it shows \(R(3,3)\gt 5\), i.e. \(n=5\) is not large enough, matching Worked Example 1's proof that \(n=6\) suffices.
Prove that \(R(r,r) \geq 2^{r/2}\) for \(r \geq 3\) is suggested by (but not proved by) the probabilistic idea sketched in the Discussion: estimate the expected number of monochromatic \(K_r\)'s in a uniformly random 2-colouring of \(K_n\), and state for which \(n\) this expectation is less than 1.
Solution
There are \(\binom{n}{r}\) subsets of size \(r\); each is monochromatic with probability \(2\cdot 2^{-\binom{r}{2}}\) (the \(2\) choices of colour, times the probability all \(\binom{r}{2}\) edges match under independent fair coin flips). By linearity of expectation, the expected number of monochromatic \(K_r\)'s is \(\binom{n}{r}\cdot 2^{1-\binom{r}{2}}\). Using \(\binom{n}{r}\leq n^r/r!\), this expectation is less than 1 once \(n^r/r! \lt 2^{\binom{r}{2}-1}\), which holds for \(n\) around \(2^{r/2}\) (up to lower-order factors); when the expectation is \(\lt 1\), some colouring of \(K_n\) has zero monochromatic \(K_r\)'s (since a nonnegative integer random variable with mean \(\lt 1\) must take the value 0 with positive probability), so \(R(r,r) \gt n\), i.e. roughly \(R(r,r)\geq 2^{r/2}\). This is Erdős's 1947 argument referenced in the Discussion; it proves existence of a good colouring without constructing one explicitly.
Suppose you are told a colouring of \(K_{17}\) has been constructed with no red \(K_4\) and no blue \(K_4\) (this is possible, since \(R(4,4)=18 \gt 17\)). What, precisely, does Ramsey's theorem let you conclude about a red/blue colouring of \(K_{18}\), and what does it not let you conclude about a colouring of \(K_{17}\) in general?
Solution
Ramsey's theorem (via \(R(4,4)=18\), quoted, not re-derived here) guarantees that every red/blue colouring of \(K_{18}\) — not just ones extending the given \(K_{17}\) colouring — contains a red \(K_4\) or a blue \(K_4\); this is an unconditional statement about all colourings of \(K_{18}\), not a consequence of the specific \(K_{17}\) example. It does not let you conclude that every colouring of \(K_{17}\) avoids a monochromatic \(K_4\) — only that at least one such colouring exists; a different, e.g. all-red, colouring of \(K_{17}\) certainly does contain a red \(K_4\) (indeed a red \(K_{17}\)). The existence of one good colouring at \(n=17\) is exactly what makes \(R(4,4)=18\) sharp (matches the upper bound of the theorem), but it says nothing about other colourings at that same \(n\).