---
title: "Ramsey Theory on Graphs"
summary: R(3,3)=6 and R(4,4)=18 with complete elementary proofs, the recursion behind every bound, and the counting argument that explains why the numbers explode.
difficulty: olympiad
tags: [ramsey, extremal, counting]
prereq: [proofs/extremal, proofs/double-count]
see: [special/coloring, complexity/npc-graphs]
---

## Ramsey numbers

:::definition label="Ramsey numbers"
$R(s,t)$ is the least $n$ such that every red/blue colouring of the edges of $K_n$ contains a red $K_s$ or a blue $K_t$. Equivalently: every graph on $n \ge R(s,t)$ vertices has a clique of size $s$ or an independent set of size $t$ (red = "edge"). Equality has two halves — *every* colouring of $K_n$ forces the monochromatic clique, and *some* colouring of $K_{n-1}$ avoids both.
:::

## The one case you can do by hand

:::theorem title="R(3,3) = 6"
Every 2-colouring of $K_6$ has a monochromatic triangle, and there is a colouring of $K_5$ with none.
:::

:::proof
*Upper bound.* Fix a vertex $v$ of $K_6$; its 5 incident edges have 3 of one colour by the pigeonhole principle, say $va, vb, vc$ red. If an edge of the triangle $abc$ is red, it completes a red triangle with $v$; otherwise $a,b,c$ span a blue triangle.
*Lower bound.* Colour $K_5$ with the red edges forming a 5-cycle: both colour classes are triangle-free, so no monochromatic triangle exists. ∎
:::

## The recursion behind every upper bound

:::note title="The only recursion needed for every upper bound"
$$R(s,t) \le R(s-1,t) + R(s,t-1), \qquad R(s,t) = R(t,s), \qquad R(2,t) = t .$$
*Proof.* Colour $K_n$ with $n = R(s-1,t) + R(s,t-1)$, and take a vertex $v$. Split its neighbours into the red set $A$ and the blue set $B$; then $|A| + |B| = n - 1$, so either $|A| \ge R(s-1,t)$ or $|B| \ge R(s,t-1)$. In the first case, $A$ contains a red $K_{s-1}$ (which together with $v$ is a red $K_s$) or a blue $K_t$; the second case is symmetric. ∎

Telescoping from $R(2,t)=t$ gives $R(s,t) \le \binom{s+t-2}{s-1}$, and hence $R(k,k) \le 4^{k+o(k)}$. One sharpening is worth knowing: if $R(s-1,t)$ and $R(s,t-1)$ are **both even**, the inequality is strict, $R(s,t) \le R(s-1,t) + R(s,t-1) - 1$ (otherwise a colouring of $K_{n-1}$ would force each vertex to have exactly $R(s-1,t)-1$ red neighbours, and the parity of the red degrees contradicts $\sum$ odd $=$ even).
:::

## Small exact values

:::theorem title="Small exact values"
$R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(4,4)=18$, $R(3,6)=18$, $R(3,7)=23$, $R(3,8)=28$, $R(3,9)=36$. $R(5,5)$ is unknown; the best published range is $43 \le R(5,5) \le 48$, and $\lim_k R(k,k)^{1/k}$ is known only to lie in $[\sqrt2,\,4]$.
:::

## Two hand-computed values: R(3,4) and R(4,4)

:::example title="R(3,4) = 9, both halves"
*Upper bound:* $R(3,4) \le R(2,4) + R(3,3) = 4 + 6 = 10$, and the parity strengthening (both terms even) gives $R(3,4) \le 9$.
*Lower bound:* on 8 vertices take the circulant graph on $\mathbb{Z}_8$ joining $i$ to $i \pm 1$ and $i+4$ (the Möbius–Kantor cubic graph). It has 8 vertices, is triangle-free, and its independence number is 3 — so it has no red triangle and no independent set of size 4, i.e. a colouring of $K_8$ with no red $K_3$ and no blue $K_4$. Hence $R(3,4) > 8$. ∎
:::

:::example title="R(4,4) = 18, both halves"
*Upper bound:* $R(4,4) \le R(3,4) + R(4,3) = 9 + 9 = 18$ (the parity trick does not apply: 9 is odd).
*Lower bound:* on 17 vertices, colour $ij$ red iff $i - j \pmod{17} \in \{\pm3, \pm5, \pm6, \pm7\}$. Every vertex has red degree 8; checking all $\binom{17}{4} = 2380$ four-sets shows that no four vertices are pairwise red-adjacent and none are pairwise blue-adjacent. So $R(4,4) \ge 18$, and with the upper bound, equality. (The check is 10 lines of code — worth running yourself once, as a reminder that "Ramsey lower bounds" are finite verifications, not mysticism.)
:::

## The probabilistic lower bound

:::theorem title="Exponential lower bound (Erdős, 1947)"
If $\binom nk 2^{1-\binom k2} < 1$ then $R(k,k) > n$. In particular $R(k,k) \ge (2^{1/2} - o(1))^k$.
:::

:::proof
Colour each of the $\binom n2$ edges red/blue independently with probability ½. For a fixed $k$-set $S$, "S is monochromatic" has probability $2 \cdot 2^{-\binom k2}$, so by the union bound
$$\Pr[\exists \text{ monochromatic } K_k] \le \binom nk 2^{1-\binom k2} < 1.$$
With positive probability no monochromatic $K_k$ exists, which proves such a colouring exists. Substituting $\binom nk \le (en/k)^k$ and $n = \lfloor 2^{k/2}\rfloor$, the exponent is $k\log_2(en/k) + 1 - \binom k2$, negative for large $k$ because $k^2/4$ dominates $k \log k$. ∎
:::

## Reading the bounds correctly

:::props title="Reading the bounds correctly"
- the argument is **non-constructive**: it shows existence by a probability estimate; derandomising it (conditional expectations) gives a polynomial-time algorithm that *finds* such a colouring for that $n$, which is still not an explicit closed-form family,
- **explicit** constructions are far weaker — Paley-type graphs give $R(k,k) \ge k^{c\log k}$, and closing the gap with $2^{k/2}$ is a central open problem,
- on the upper side, $R(k,k) \le (4 - o(1))^k$ (Sah, 2023) is the first asymptotic improvement over the classical $4^k$ in decades, while the lower bound has stayed at $(\sqrt2)^{k}$ since Bohman–Keevash,
- the same computation with unequal sizes — $\binom ns 2^{-\binom s2} + \binom nt 2^{-\binom t2} < 1 \Rightarrow R(s,t) > n$ — is how you prove "there exists a graph with no $K_4$ and with independence number at most 4 on $n$ vertices", which is what many "show the bound is tight" problems actually ask.
:::

## How the arguments appear in contests

:::props title="How these arguments appear in contests"
- **"6 people, 3 mutual friends or 3 mutual strangers"** — the $R(3,3)=6$ pigeonhole paragraph; the only idea is which vertex to fix (usually the one of largest degree),
- **three colours**: $R(3,3,3) = 17$. Upper bound: in any 3-colouring of $K_{17}$ some vertex has at least $\lceil 16/3 \rceil = 6$ incident edges of one colour, and $R(3,3)=6$ inside that neighbourhood gives the monochromatic triangle. Lower bound: a 3-colouring of $K_{16}$ with no monochromatic triangle (two copies of the $K_5$ construction glued appropriately) — the arithmetic $\lceil 16/3 \rceil = 6$ versus the mistaken $\lceil 16/3 \rceil = 5$ is the standard slip,
- **sequence form**: Erdős–Szekeres below, which is the same proof pattern (labels, distinctness, count),
- **algorithmic extraction**: the upper bound implies every graph on $n$ vertices has a clique or independent set of size $\ge \log_2 n$, and the proof is recursive — at a vertex $v$ of degree $\ge n/2$ recurse into $N(v)$, else into the non-neighbours — giving a linear-time algorithm for a $\log n$-sized homogeneous set,
- **why "large homogeneous set" is a lower-bound tool**: branching programs, range-query structures, and Ramsey-type arguments in geometry all use "either structure of size $\log n$ or nothing", so a $\log$ from Ramsey shows up in an $n^{\Omega(\log n)}$ bound.
:::

## Erdős–Szekeres

:::example title="Erdős–Szekeres (1935)"
Any sequence of $ab + 1$ distinct real numbers contains an increasing subsequence of length $a+1$ or a decreasing subsequence of length $b+1$.
*Proof.* Label position $i$ with $(\ell_i, d_i)$ = the lengths of the longest increasing and longest decreasing subsequence ending at $i$. If $i < j$ and $x_i < x_j$ then $\ell_j \ge \ell_i + 1$; if $i < j$ and $x_i > x_j$ then $d_j \ge d_i + 1$. So no two positions share a label. But only $ab$ labels lie in $[a] \times [b]$, so with $ab + 1$ positions some label escapes the box, giving the claim. The case $a = b = k$ ("$k^2 + 1$ numbers force a monotone subsequence of length $k+1$") is tight: take $k$ decreasing blocks of size $k$, arranged in increasing order. ∎
:::

## Four precision points

:::warning title="Four precision points"
1. A Ramsey *value* claim needs both directions; a solution that only proves "every colouring of $K_6$ works" has proved $R(3,3) \le 6$.
2. In the recursion, the pigeonhole split is on the neighbourhood of one vertex — the sets are $|A| + |B| = n - 1$, so the threshold is $\lceil (n-1)/2 \rceil$, not $n/2$.
3. The probabilistic bound gives existence for **some** $n \approx 2^{k/2}$; it never says "for all $n$" or "the graph is random-like" — a common overclaim in write-ups.
4. If a problem asks for an *explicit* example, use the algebraic route (Paley graph on $q \equiv 1 \pmod 4$ vertices: self-complementary, and every clique and independent set has size at most $\sqrt q$ by the character-sum bound) — that is 4 lines and provable; do not try to "construct" from the probabilistic method.
:::

:::note title="Two more facts worth having in your pocket"
- **the true order of $R(3,t)$**: telescoping the recursion gives $R(3,t) \le \binom{t}{2} + 1$, and the probabilistic method gives the matching-order lower bound up to a logarithm, $R(3,t) \ge c\, t^2 / \log t$ (Ajtai–Komlós–Szemerédi and Kim). So the quadratic bound is off by exactly a $\log$ — worth knowing before claiming an "optimal" construction in an essay answer,
- **monochromatic triangles are unavoidable in quantity**: any 2-colouring of $K_n$ has at least $\left(\tfrac14 - o(1)\right)\binom n3$ monochromatic triangles (Goodman), and the random colouring attains it. Proof by double counting: count the "non-mono"cheromatic wedges $\binom{n}{2}$-wise, i.e. for each vertex count pairs of incident edges of different colours and sum — @proofs/double-count's exact technique. It is the one Ramsey-adjacent inequality that is both easy and asked in finals.
:::