Part 19: Extremal Graph Theory & Ramsey Theory

A Bit of History

Frank P. Ramsey, a brilliant Cambridge mathematician, economist, and philosopher, proved the foundational theorem of this field in a 1930 paper on formal logic — published only after his tragically early death at age 26 from complications following surgery. He likely never anticipated that a lemma buried inside a paper about decision procedures would spawn an entire branch of combinatorics bearing his name.

Decades later, Paul Erdős (whose name recurs throughout this series) became the field's greatest champion, popularizing the "party problem" framing and using probabilistic arguments — the probabilistic method he pioneered in a 1947 paper — to prove lower bounds on Ramsey numbers that remain, remarkably, close to the best known bounds today.

The complementary "how dense can a graph be while still avoiding a forbidden pattern" question was answered independently by Pál Turán, a Hungarian mathematician who developed his eponymous 1941 theorem while imprisoned in a forced-labor camp during World War II — a haunting historical detail Turán himself later described, noting that mathematics offered him a form of escape and dignity during that period.

Ramsey's Theorem

Ramsey's theorem, informally: for any given structure size, if a large enough complete graph has its edges colored with a fixed number of colors, a monochromatic complete subgraph of the desired size is guaranteed to exist — no coloring, however cleverly designed, can avoid it. Formally, for any integers \(r, s\), there exists a smallest integer \(R(r,s)\) — the Ramsey number — such that any 2-coloring (say, red/blue) of the edges of the complete graph \(K_{R(r,s)}\) contains either a red \(K_r\) or a blue \(K_s\).

The Party Problem

The classic illustration: model a party as a complete graph where each pair of guests is connected by an edge colored "friends" or "strangers." The claim \(R(3,3) = 6\) says that among any 6 people, there must be either 3 mutual friends or 3 mutual strangers — but with only 5 people, this can fail (a specific 5-person friendship pattern, the 5-cycle, has no monochromatic triangle in either color). This is provable by a short, elegant pigeonhole argument: pick any one person; among the other 5, at least 3 must be connected to them by edges of the same color (say, "friends," by pigeonhole since \(5 = 3+2\)); if any two of those 3 are also friends, those two plus the original person form a friend-triangle; if none of those 3 are friends with each other, those 3 themselves form a stranger-triangle. Either way, a monochromatic triangle is unavoidable.

Ramsey Numbers & Their Growth

Ramsey numbers are notoriously difficult to compute exactly — only a handful of small values are known precisely (\(R(3,3)=6\), \(R(3,4)=9\), \(R(4,4)=18\)), and even \(R(5,5)\) remains unknown to this day, pinned only between 43 and 46 by decades of effort. Paul Erdős famously joked (as retold by Ronald Graham) that if aliens threatened to destroy Earth unless we could tell them \(R(5,5)\), humanity should marshal every computer and every mathematician to find it — but if they demanded \(R(6,6)\), our best strategy would be to attack the aliens first, since the number is considered permanently beyond reach.

Erdős's own 1947 probabilistic-method proof gives an exponential lower bound on diagonal Ramsey numbers \(R(k,k)\) — showing a random 2-coloring of a graph smaller than roughly \(2^{k/2}\) vertices has, with positive probability, no monochromatic \(K_k\) at all, without ever constructing such a coloring explicitly. This non-constructive style of argument was itself revolutionary: proving something exists by showing the probability of its existence is positive, without exhibiting a single example.

Turán's Theorem

Where Ramsey theory asks "how large must a graph be to force a substructure," extremal graph theory asks the complementary density question: "how many edges can a graph have while still avoiding a forbidden substructure?" Turán's theorem answers this precisely for the simplest forbidden substructure, a complete graph \(K_{r+1}\):

For the simplest case \(r=2\) (avoiding triangles, \(K_3\)), Turán's theorem specializes to a much older result — Mantel's theorem (1907) — which states the maximum triangle-free graph on \(n\) vertices is the complete bipartite graph \(K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}\), with \(\lfloor n^2/4 \rfloor\) edges.

The Erdős–Stone Theorem

Turán's theorem pins down the exact extremal edge count for avoiding complete graphs, but what about avoiding an arbitrary graph \(H\)? The Erdős–Stone theorem (Erdős and Arthur Stone, 1946) answers this asymptotically, connecting extremal density directly to the chromatic number of the forbidden graph \(H\):

$$\text{ex}(n, H) = \left(1 - \frac{1}{\chi(H)-1} + o(1)\right)\binom{n}{2}$$

where \(\text{ex}(n,H)\) is the maximum number of edges an \(H\)-free graph on \(n\) vertices can have, and \(\chi(H)\) is the chromatic number of \(H\) from Part 13. This single formula elegantly ties together three separate parts of this series — extremal density, Ramsey-style avoidance, and graph coloring — into one asymptotic statement.

Real-World Applications

Exercises

1. Reproduce the pigeonhole argument showing \(R(3,3) \leq 6\) by hand, drawing out the case analysis for a specific 6-vertex 2-colored graph.
2. Verify that the 5-cycle \(C_5\), with edges colored so that the cycle itself is "red" and all diagonals are "blue," has no monochromatic triangle — confirming \(R(3,3) > 5\), i.e., \(R(3,3)=6\) exactly.
3. Using Mantel's theorem, compute the maximum number of edges a triangle-free graph on 10 vertices can have, and describe the extremal graph explicitly.
4. Challenge: Look up the current best-known bounds for \(R(5,5)\) and briefly research why closing this gap has resisted decades of computational and theoretical effort.

Conclusion & Next Steps

Ramsey and extremal graph theory reveal a profound truth: structure is unavoidable at scale, whether you're looking for it or desperately trying to avoid it. The next part takes this "structure emerges from scale" idea in a different direction — using randomness itself as a tool, and studying what typical (rather than worst-case or best-case) graphs look like.