Ramsey Theory — R(3,3) & Applications in Competitive Programming
The Party Problem
Imagine you are hosting a dinner party and you invite six people. Among any pair of guests, they are either friends (they know each other) or strangers (they don't). Here is a surprising fact:
To see why, pick any person — call them Alice. Alice has 5 relationships (one with each other guest), and each relationship is either "friend" or "stranger." By the Pigeonhole Principle, at least ⌈5/2⌉ = 3 of these relationships must be the same type. Suppose Alice is friends with (at least) Bob, Carol, and Dave.
Now consider the relationships among Bob, Carol, and Dave:
- If any pair among them are friends — say Bob and Carol — then Alice, Bob, and Carol form a triangle of mutual friends. Done.
- If none of them are friends with each other, then Bob, Carol, and Dave form a triangle of mutual strangers. Done.
The same argument works if Alice has 3 or more strangers instead. Either way, we always find a monochromatic triangle.
This is the simplest nontrivial instance of Ramsey Theory: the study of conditions under which order must appear in sufficiently large structures. The branch is named after Frank P. Ramsey, who proved the foundational theorem in 1930.
We can model this problem with graph theory. Represent the 6 guests as vertices of the complete graph K6, and colour each edge red (friend) or blue (stranger). The party theorem says every 2-colouring of K6 contains a monochromatic triangle (K3). In Ramsey notation: R(3, 3) = 6.
Why 5 Is Not Enough
To confirm that R(3, 3) ≠ 5, we need a 2-colouring of K5 with no monochromatic triangle. The cycle C5 works: colour the 5 edges of the cycle red and the 5 remaining edges blue. Both the red graph and the blue graph form a C5, and a 5-cycle contains no triangle. So R(3, 3) > 5, and combined with our proof above, R(3, 3) = 6.
Ramsey Numbers
Definition
For positive integers s and t (both ≥ 2), the Ramsey number R(s, t) is the smallest integer n such that every 2-colouring of the edges of Kn contains either a red Ks or a blue Kt.
Ramsey's theorem guarantees that R(s, t) is finite for all s, t ≥ 2. The challenge is determining its exact value — a notoriously difficult problem.
The Recursive Bound
The key inequality that powers most upper-bound proofs is:
R(s, t) ≤ R(s − 1, t) + R(s, t − 1)
Proof sketch. Consider any 2-colouring of Kn where n = R(s − 1, t) + R(s, t − 1). Pick a vertex v. It has n − 1 neighbours. Partition them into set A (red neighbours of v) and set B (blue neighbours of v). Since |A| + |B| = n − 1 = R(s − 1, t) + R(s, t − 1) − 1, either |A| ≥ R(s − 1, t) or |B| ≥ R(s, t − 1).
- If |A| ≥ R(s − 1, t): the subgraph on A contains a red Ks−1 or a blue Kt. A red Ks−1 plus v gives a red Ks.
- If |B| ≥ R(s, t − 1): symmetrically, we get a blue Kt or a red Ks.
With base cases R(s, 2) = s and R(2, t) = t, unrolling this recurrence gives the Erdős–Szekeres upper bound:
R(s, t) ≤ C(s + t − 2, s − 1)
Proof That R(3, 3) = 6
Applying the recursive bound: R(3, 3) ≤ R(2, 3) + R(3, 2) = 3 + 3 = 6. We showed above that R(3, 3) > 5. Therefore R(3, 3) = 6. ∎
Known Ramsey Numbers
Computing exact Ramsey numbers is extraordinarily hard. Erdős famously said that if aliens demanded we compute R(5, 5) or they'd destroy Earth, we should try to compute it — but if they demanded R(6, 6), we should prepare for war. Here are the known values:
| s \ t | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|
| 3 | 6 | 9 | 14 | 18 | 23 | 28 | 36 |
| 4 | 9 | 18 | 25 | 36–41 | 49–61 | 56–84 | 73–115 |
| 5 | 14 | 25 | 43–48 | 58–87 | 80–143 | 101–216 | 126–316 |
Most entries for s, t ≥ 5 are only known as ranges. The exact value of R(5, 5) is still open — we only know 43 ≤ R(5, 5) ≤ 48.
Symmetry and Monotonicity
Two useful properties:
- Symmetry: R(s, t) = R(t, s) — just swap the two colours.
- Monotonicity: R(s, t) ≤ R(s + 1, t) — if every colouring of Kn has a red Ks or blue Kt, the same is true for red Ks+1.
Proof Techniques
Pigeonhole Arguments
The R(3, 3) = 6 proof above is the archetype: pick a vertex, pigeonhole its neighbours by colour, then recurse on the resulting subsets. This strategy extends to larger Ramsey numbers. For example, to prove R(3, 4) ≤ 9:
Take any 2-colouring of K9. Pick vertex v with 8 neighbours. Either v has ≥ 4 red neighbours (leading to a red K3 or blue K4 among them, since R(2, 4) = 4) or v has ≥ 6 blue neighbours (leading to a red K3 or blue K3 among them, since R(3, 3) = 6, and a blue K3 plus v gives a blue K4).
The Probabilistic Method (Erdős Lower Bound)
In 1947, Erdős gave a revolutionary non-constructive proof of a lower bound for diagonal Ramsey numbers using the probabilistic method:
In particular, R(k, k) grows exponentially.
Proof. Colour each edge of Kn red or blue independently and uniformly at random. For any fixed set S of k vertices, the probability that S is monochromatic (all red or all blue) is:
P(S monochromatic) = 2 · (1/2)C(k,2) = 21 − C(k,2)
By the union bound over all C(n, k) possible k-subsets:
P(∃ monochromatic Kk) ≤ C(n, k) · 21 − C(k,2)
If this probability is strictly less than 1, there exists a colouring with no monochromatic Kk, so R(k, k) > n. Using C(n, k) < nk/k! and simplifying, we get R(k, k) > n whenever nk · 21 − C(k,2) / k! < 1. Choosing n = ⌊2k/2⌋ satisfies this for k ≥ 3.
Constructive vs. Existence Proofs
The probabilistic method tells us R(k, k) > 2k/2 but does not construct an explicit colouring witnessing this. Finding explicit constructions that match probabilistic bounds is a major open problem.
Existence (Probabilistic)
- Shows a valid colouring exists
- Does not tell you what it looks like
- Gives R(k,k) > 2k/2
- Simple elegant proof
Constructive
- Exhibits an explicit colouring
- Usually weaker bounds
- Best known: R(k,k) > 2k/2 − o(k) (Paley graphs, etc.)
- Algebraic or number-theoretic
The best known constructive lower bounds use Paley graphs: take the vertices to be elements of a finite field Fq (q ≡ 1 mod 4, q prime), and connect two vertices if their difference is a quadratic residue. These give triangle-free graphs (hence Ramsey lower bounds) of size roughly √q.
Ramsey Theory Generalizations
Ramsey theory extends far beyond graph colourings. Several landmark theorems share the same philosophical core: complete disorder is impossible in sufficiently large structures.
Schur Numbers
Schur's Theorem (1916). For every positive integer r, there exists a smallest integer S(r) — the Schur number — such that for any r-colouring of {1, 2, …, S(r)}, there exist x, y, z (not necessarily distinct, with x + y = z) that are all the same colour.
Known values: S(1) = 2, S(2) = 5, S(3) = 14, S(4) = 45. S(5) was determined in 2017 to be 161 by a massive SAT-solver computation.
Van der Waerden's Theorem
Van der Waerden (1927). For any positive integers r and k, there exists a smallest integer W(r, k) such that any r-colouring of {1, 2, …, W(r, k)} contains a monochromatic arithmetic progression of length k.
Known values include W(2, 3) = 9, W(2, 4) = 35, W(2, 5) = 178, W(2, 6) = 1132. The growth rate is immense — van der Waerden numbers grow faster than any polynomial but the exact rate remained open until Gowers proved an effective bound in 2001.
Hales–Jewett Theorem
Hales–Jewett (1963). For any positive integers r and k, there exists a dimension n such that any r-colouring of the k-ary n-dimensional cube {1, …, k}n contains a monochromatic combinatorial line — a set of k points where each coordinate either stays constant or varies together through all values 1, …, k.
This is the "mother of all Ramsey theorems" in combinatorics. Van der Waerden's theorem follows as a corollary. The polymath project (2009) gave the first elementary proof of the density version (density Hales–Jewett theorem).
The Erdős–Szekeres Theorem
While often stated independently, the Erdős–Szekeres theorem is closely connected to Ramsey theory:
Proof via Ramsey. Given a sequence a1, …, an, define a 2-colouring of Kn: colour edge (i, j) with i < j red if ai < aj (increasing), blue if ai > aj (decreasing). A red Kr is an increasing subsequence of length r; a blue Ks is a decreasing subsequence of length s. Ramsey's theorem guarantees one of these exists for large enough n.
The exact bound (r − 1)(s − 1) + 1 is tighter than the Ramsey bound R(r, s), because the 2-colouring here is transitive (it arises from a total order), which imposes much more structure.
Algorithmic Aspects
The Search Problem
Given a 2-coloured complete graph Kn, how quickly can we find a monochromatic clique of a given size? And how do we verify whether a particular colouring avoids monochromatic Ks?
Brute-Force Clique Checking
For small n (say n ≤ 20), we can enumerate all C(n, s) subsets and check if any is monochromatic. The complexity is O(C(n, s) · C(s, 2)).
Adjacency Matrix Representation
For competitive programming, represent a 2-coloured Kn as an n × n adjacency matrix or — for n ≤ 64 — as an array of bitmasks. Then checking whether a set of vertices forms a monochromatic clique reduces to bitwise AND operations.
If red[i] is a bitmask of i's red neighbours, a set S forms a red clique
iff for every vertex v in S, S ∖ {v} ⊆ red[v]. With bitmasks we can test
this in O(|S|) time.
Backtracking Search
To find all Ramsey colourings (colourings of Kn avoiding monochromatic Ks and Kt), we use backtracking. Assign colours edge by edge, pruning whenever a monochromatic clique forms. Symmetry-breaking (fixing the first vertex's edges, using graph automorphisms) reduces the search space dramatically.
Modern Ramsey number computations combine backtracking with SAT solvers. The determination of R(4, 5) = 25 by McKay and Radziszowski (1995) was a landmark computational achievement.
CP Applications
Ramsey theory rarely appears as "compute R(s, t)" in contests. Instead, it surfaces through three main patterns:
Pattern 1: Pigeonhole Existence Arguments
The most common competitive-programming use of Ramsey-type reasoning is the pigeonhole argument: given n objects with some binary relation, when n is large enough, a specific structure must exist.
Example. "Given 6 points in the plane, no three collinear, prove that some 3 form an acute triangle or some 3 form an obtuse triangle." This is essentially an R(3, 3) argument in disguise.
Pattern 2: The n ≥ R(s, t) Observation
Some problems give you a graph or structure with n vertices and ask you to find a clique or independent set. If n ≥ R(s, t), you can guarantee a clique of size s or independent set of size t exists.
Example. "Given a tournament on n ≥ 8 vertices, show there exist 3 vertices that form a directed 3-cycle, or 3 vertices where one beats both others who in turn have a specific relationship."
Pattern 3: Erdős–Szekeres for Monotone Subsequences
This is by far the most practically important Ramsey-adjacent result in CP. The Erdős–Szekeres theorem tells us:
The classic application is the Longest Increasing Subsequence (LIS) problem. By Erdős–Szekeres, a sequence of length n2 + 1 always has a monotone subsequence of length n + 1. More importantly, the proof gives us the algorithm:
- Assign to each element ai the pair (lisi, ldsi) where lisi = length of the longest increasing subsequence ending at i, and ldsi = longest decreasing subsequence ending at i.
- All pairs are distinct (if i < j and ai < aj, then lisj > lisi; if ai > aj, then ldsj > ldsi).
- If lisi ≤ r − 1 for all i, then all lds values are distinct within each "lis-bucket," forcing some lds ≥ s.
Pattern 4: Constructive Ramsey in Interactive Problems
Some interactive problems ask you to query edges of a hidden graph and find a monochromatic clique. Knowing that R(3, 3) = 6 means you only need 6 vertices to guarantee finding a monochromatic triangle, and the pigeonhole proof gives you the algorithm: pick a vertex, classify its neighbours by colour, recurse.
Classic Contest Problems
- LIS (Longest Increasing Subsequence) — O(n log n) algorithm directly connected to Erdős–Szekeres. Appears in hundreds of CP problems.
- Codeforces 553E — Kyoya and Train — Uses pigeonhole-style reasoning on subsequences.
- Tournament problems — Many ask you to find specific substructures in tournaments; Ramsey guarantees existence when n is large.
- IMO 1964 Problem 4 — Prove that among any 17 people, either there exist 3 mutual acquaintances or 3 mutual strangers forming a specific configuration.
C++ Toolkit
Finding a Monochromatic Triangle in K6
Given a 2-colouring of K6 (stored as a bitmask adjacency), the pigeonhole proof directly translates into an algorithm. This runs in O(1) since n = 6 is fixed.
#include <bits/stdc++.h>
using namespace std;
// adj[i] = bitmask of red neighbours of vertex i (0-indexed, 6 vertices)
// Returns a triple {a, b, c} forming a monochromatic triangle.
// colour = 0 means red triangle, colour = 1 means blue triangle.
struct TriResult { int a, b, c, colour; };
TriResult findMonoTriangle(int adj[6]) {
// Pick vertex 0. It has 5 neighbours.
int redN = adj[0] & 0b111110; // red neighbours (bits 1..5)
int blueN = (~adj[0]) & 0b111110; // blue neighbours
int rcnt = __builtin_popcount(redN);
int pick_mask, pick_colour;
if (rcnt >= 3) {
pick_mask = redN;
pick_colour = 0; // looking for red triangle
} else {
pick_mask = blueN;
pick_colour = 1; // looking for blue triangle
}
// Extract 3 vertices from pick_mask
int verts[3], vi = 0;
for (int b = 1; b < 6 && vi < 3; b++)
if (pick_mask & (1 << b)) verts[vi++] = b;
// Check pairs among verts[0..2]
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 3; j++) {
int u = verts[i], v = verts[j];
bool isRed = (adj[u] >> v) & 1;
bool sameColour = (pick_colour == 0) ? isRed : !isRed;
if (sameColour) {
// {0, u, v} is monochromatic
return {0, u, v, pick_colour};
}
}
}
// If no pair matches, the three vertices form a
// monochromatic triangle of the OTHER colour
return {verts[0], verts[1], verts[2], 1 - pick_colour};
}
int main() {
// Example: C5 red + complement blue on K6
// (vertex 5 is connected to all by both colours for K6)
int adj[6];
// Encode your colouring here; for demo, use a random colouring
// adj[i] bit j = 1 means edge (i,j) is red
adj[0] = 0b010010; adj[1] = 0b100101;
adj[2] = 0b001010; adj[3] = 0b010100;
adj[4] = 0b101000; adj[5] = 0b000001;
auto [a, b, c, col] = findMonoTriangle(adj);
cout << "Monochromatic triangle: {" << a << ", "
<< b << ", " << c << "} colour="
<< (col == 0 ? "red" : "blue") << "\n";
return 0;
}Brute-Force Ramsey Verification
Given n and s, check whether there exists a 2-colouring of Kn that avoids monochromatic Ks. This is only feasible for very small n (say n ≤ 10 and s = 3 or 4).
#include <bits/stdc++.h>
using namespace std;
int N, S;
// Check if the subset 'mask' of size S forms a monochromatic clique
// in the colouring given by edge_colour.
// edge_colour: flatten upper triangle, edge (i,j) with i<j at index i*N - i*(i+1)/2 + j - i - 1
bool isMonoClique(vector<int>& verts, vector<int>& edge_colour) {
bool allRed = true, allBlue = true;
for (int i = 0; i < (int)verts.size() && (allRed || allBlue); i++) {
for (int j = i + 1; j < (int)verts.size(); j++) {
int u = verts[i], v = verts[j];
int idx = u * N - u * (u + 1) / 2 + v - u - 1;
if (edge_colour[idx] == 0) allBlue = false;
else allRed = false;
}
}
return allRed || allBlue;
}
bool hasMonoClique(vector<int>& edge_colour) {
// Enumerate all C(N, S) subsets
vector<int> verts(S);
function<bool(int, int)> enumerate = [&](int start, int depth) -> bool {
if (depth == S)
return isMonoClique(verts, edge_colour);
for (int i = start; i < N; i++) {
verts[depth] = i;
if (enumerate(i + 1, depth + 1)) return true;
}
return false;
};
return enumerate(0, 0);
}
int main() {
// Verify R(3,3) > 5 by finding a colouring of K5 with no mono-K3
N = 5; S = 3;
int E = N * (N - 1) / 2; // 10 edges
for (int mask = 0; mask < (1 << E); mask++) {
vector<int> ec(E);
for (int i = 0; i < E; i++)
ec[i] = (mask >> i) & 1;
if (!hasMonoClique(ec)) {
cout << "Found colouring of K" << N
<< " with no monochromatic K" << S << ":\n";
int idx = 0;
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
cout << " (" << i << "," << j << ") = "
<< (ec[idx++] ? "blue" : "red") << "\n";
return 0;
}
}
cout << "No valid colouring exists: R(" << S << "," << S
<< ") <= " << N << "\n";
return 0;
}Erdős–Szekeres via LIS (O(n log n))
The most contest-relevant algorithm connected to Ramsey theory: find the longest increasing subsequence. By Erdős–Szekeres, if LIS has length < r, then the longest decreasing subsequence (LDS) has length ≥ ⌈n / (r − 1)⌉.
#include <bits/stdc++.h>
using namespace std;
// O(n log n) LIS returning the actual subsequence
vector<int> lis(const vector<int>& a) {
int n = a.size();
vector<int> dp, pos(n), parent(n, -1);
// dp[i] = smallest tail of increasing subsequence of length i+1
for (int i = 0; i < n; i++) {
auto it = lower_bound(dp.begin(), dp.end(), a[i]);
int idx = it - dp.begin();
if (it == dp.end()) dp.push_back(a[i]);
else *it = a[i];
pos[i] = idx;
if (idx > 0) {
// find predecessor: last element placed at position idx-1
for (int j = i - 1; j >= 0; j--) {
if (pos[j] == idx - 1 && a[j] < a[i]) {
parent[i] = j;
break;
}
}
}
}
// Reconstruct
int len = dp.size();
vector<int> result;
int cur = -1;
for (int i = n - 1; i >= 0; i--)
if (pos[i] == len - 1) { cur = i; break; }
while (cur != -1) {
result.push_back(a[cur]);
cur = parent[cur];
}
reverse(result.begin(), result.end());
return result;
}
// LDS by negating and running LIS
vector<int> lds(const vector<int>& a) {
vector<int> neg(a.size());
for (int i = 0; i < (int)a.size(); i++) neg[i] = -a[i];
auto res = lis(neg);
for (auto& x : res) x = -x;
return res;
}
int main() {
// Erdős–Szekeres demo: sequence of length 10
// Must have increasing subseq of length 4 or decreasing of length 4
// (since 10 > 3*3 = 9)
vector<int> seq = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
auto inc = lis(seq);
auto dec = lds(seq);
cout << "Sequence: ";
for (int x : seq) cout << x << " ";
cout << "\n";
cout << "LIS (length " << inc.size() << "): ";
for (int x : inc) cout << x << " ";
cout << "\n";
cout << "LDS (length " << dec.size() << "): ";
for (int x : dec) cout << x << " ";
cout << "\n";
int n = seq.size();
int r = inc.size(), s = dec.size();
cout << "Erdős–Szekeres check: n=" << n
<< " > (r-1)(s-1)=" << (r-1)*(s-1)
<< "? " << (n > (r-1)*(s-1) ? "YES" : "NO") << "\n";
return 0;
}Utility: Counting Monochromatic Cliques with Bitmasks
When n is small enough (n ≤ 20–25), bitmask enumeration is a powerful technique for Ramsey-related problems:
// Count monochromatic K_s in a 2-coloured K_n (bitmask approach)
// red[i] = bitmask of red neighbours of vertex i
int countMonoCliques(int n, int s, long long red[]) {
int count = 0;
// Enumerate all subsets of size s using Gosper's hack
long long mask = (1LL << s) - 1;
while (mask < (1LL << n)) {
// Check if mask forms a red clique
bool isRed = true, isBlue = true;
long long tmp = mask;
while (tmp && (isRed || isBlue)) {
int v = __builtin_ctzll(tmp);
long long others = mask ^ (1LL << v);
if ((red[v] & others) != others) isRed = false;
if ((~red[v] & others) != others) isBlue = false;
tmp &= tmp - 1;
}
if (isRed || isBlue) count++;
// Gosper's hack: next subset of same size
long long c = mask & (-mask);
long long r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
return count;
}Summary
| Concept | Key Fact | CP Relevance |
|---|---|---|
| R(3, 3) = 6 | Every 2-colouring of K6 has a monochromatic triangle | Party problem, pigeonhole arguments |
| Recursive bound | R(s,t) ≤ R(s−1,t) + R(s,t−1) | Proving upper bounds on small Ramsey numbers |
| Erdős lower bound | R(k,k) > 2k/2 | Understanding limits, probabilistic method |
| Erdős–Szekeres | Seq of length > (r−1)(s−1) ⟹ mono subseq | LIS/LDS problems — very common |
| Schur numbers | Monochromatic x + y = z in coloured integers | Number theory + colouring hybrids |
| Van der Waerden | Monochromatic AP in coloured integers | Rare but appears in olympiad-style problems |
What's next? In the next post, we explore Extremal Combinatorics — the Turán-style question of "what is the maximum number of edges in a graph avoiding Kr?" — which is the natural quantitative follow-up to Ramsey theory.