Ramsey Theory and Extremal Combinatorics

The pigeonhole principle says that enough objects force a repeat. Ramsey theory is its grown-up form, and its slogan is unforgettable: complete disorder is impossible. No matter how you try to scramble a large enough structure, some orderly pattern is unavoidable. You cannot make a big system with no structure at all — order is not something you build in, it is something you cannot keep out.

The classic statement is the party problem. Among any 6 people, there are always either 3 who all know each other, or 3 who are all mutual strangers. Model it as a graph: 6 dots (people), every pair joined by an edge, coloured red for "friends" or blue for "strangers". The claim is that any red/blue colouring of all \binom{6}{2} = 15 edges of the complete graph K_6 contains a monochromatic triangle — three dots with all three connecting edges the same colour. And it is sharp: with only 5 people you can arrange a colouring with no such triangle.

The unavoidable triangle in K₆

Here is the pigeonhole heart of the proof. Pick any vertex; it has 5 edges in two colours, so by pigeonhole at least \lceil 5/2 \rceil = 3 of them share a colour — say red, to three neighbours u, v, w. Now look at the triangle among u, v, w: if any of its three edges is red, that edge plus our vertex makes a red triangle; if none is red, then u, v, w form a blue triangle. Either way, a monochromatic triangle exists. Step through the figure to see one.

Ramsey numbers are monstrously hard

You would think that after R(3,3) = 6 the rest would follow. They do not. The next one, R(4,4) = 18, was found — but R(5,5) is still unknown, pinned only somewhere between 43 and 48 despite decades of computer search. The difficulty grows so fast that the mathematician Paul Erdős offered a famous parable:

Erdős imagined an alien force landing and demanding the value of R(5,5), threatening to destroy Earth otherwise. His advice: marshal every mathematician and every computer on the planet and try to compute it. But if instead they demanded R(6,6), he said, "we should attempt to destroy the aliens." The number of colourings to check grows so astronomically that brute force is hopeless — a vivid reminder that "this exists and is finite" (which Ramsey's theorem guarantees) is a world away from "we can compute it".

The reason existence is easy but values are hard is that the lower bounds come from finding clever colourings with no monochromatic clique, and good colourings are astonishingly hard to build — the best known come from Erdős's probabilistic method, which proves a good colouring exists by showing a random one works with positive probability, without ever exhibiting it.

Extremal combinatorics: how much before structure is forced?

Ramsey theory asks "how big must a structure be to force a pattern?" Its close cousin, extremal combinatorics, asks the quantitative version: "how many edges (or sets, or elements) can you have before a pattern is forced?" The prototype is Mantel's theorem (a special case of Turán's theorem).

A graph on n vertices with no triangle has at most \left\lfloor \dfrac{n^2}{4} \right\rfloor edges — and this maximum is achieved uniquely by the complete balanced bipartite graph K_{\lfloor n/2\rfloor,\,\lceil n/2\rceil} (split the vertices into two equal halves and join every cross-pair).

So if a graph on n = 10 vertices has more than \lfloor 100/4 \rfloor = 25 edges, it is forced to contain a triangle — no matter how the edges are arranged. Split ten people into two groups of five and join every cross-pair and you get exactly 25 triangle-free edges; add one more and a triangle appears. The bipartite split is the "most edges without a triangle" configuration, and Turán's theorem generalises it to forbidding any complete graph K_r. This boundary between "possible" and "forced" is the whole spirit of extremal combinatorics — and a fitting summit for the module.