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.
Two Complementary Questions: Force vs. Avoid
Ramsey theory and extremal graph theory look in opposite directions, but they are asking about the same tension. Ramsey theory asks how large a system must become before a desired pattern is unavoidable under every coloring. Extremal graph theory fixes one forbidden pattern and asks how dense a graph can become while still avoiding it. One studies the threshold where structure is forced; the other studies the densest possible world just below that threshold.
Same phenomenon, viewed from opposite sides
Imagine structure as pressure building inside a graph. Ramsey theory asks when that pressure guarantees a pattern somewhere. Extremal theory asks how many edges you can pack in before the forbidden pattern becomes impossible to avoid.
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\).
Read the Definition as a Worst-Case Guarantee
The phrase every coloring is doing the heavy lifting. You are not trying to find one coloring that creates structure; an adversary may color the edges specifically to avoid it. The Ramsey number is the first size at which even the cleverest avoidance strategy must fail.
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.
The pigeonhole step creates a three-person test set
Pick one guest, call them P. Five edges leave P. With only two colors, at least three of those five edges share a color. Suppose three are red. Now look only at the three endpoints: if any edge among them is red, it completes a red triangle with P; if none is red, all three mutual edges are blue, forming a blue triangle.
Why 5 people are not enough: the cycle coloring dodges both triangles
To prove the exact value is 6, we also need a coloring of K₅ with no monochromatic triangle. Color the five cycle edges red and all five diagonals blue. The red graph is a 5-cycle, so it has no triangle; the blue graph is also a 5-cycle, so it has no triangle either.
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.
The Probabilistic Method: Proving Existence Without Building the Example
Erdős's lower-bound argument uses randomness as a proof device. Color every edge of \(K_n\) red or blue independently with probability \(1/2\). For any fixed set of \(k\) vertices, the probability that all \(\binom{k}{2}\) edges among them receive the same color is
There are \(\binom{n}{k}\) candidate \(k\)-vertex sets, so the expected number of monochromatic \(K_k\)'s is
If this expectation is less than 1, then not every coloring can contain at least one bad clique — otherwise the average would be at least 1. Therefore some coloring must contain zero monochromatic \(K_k\)'s. That proves a lower bound on \(R(k,k)\) without ever explicitly constructing the coloring.
“Expected bad structures < 1” forces a good coloring to exist
Why “Expected Value < 1” Is So Powerful
If every coloring had at least one monochromatic \(K_k\), then the expected count across random colorings could not be below 1. So an expectation below 1 is already a contradiction to universal badness. This tiny averaging argument is the core of the probabilistic method.
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}\):
Turán's Theorem (1941)
Among all graphs on \(n\) vertices containing no \(K_{r+1}\) subgraph, the maximum number of edges is achieved uniquely by the Turán graph \(T(n,r)\) — the complete \(r\)-partite graph with parts as equal in size as possible. No \(K_{r+1}\)-free graph on \(n\) vertices can have more edges than this construction.
The extremal construction is balanced because putting two vertices into the same part removes their connecting edge; spreading vertices as evenly as possible minimizes the number of missing within-part edges. If the part sizes are \(n_1,\ldots,n_r\), then
To avoid a large clique, split vertices into balanced independent groups
In \(T(n,r)\), vertices inside the same part are not adjacent, while every pair in different parts is adjacent. Any clique can use at most one vertex from each part, so a \(K_{r+1}\) is impossible. Balancing the parts keeps as many cross-part edges as possible.
Why Balance Is Optimal
If one part is much larger than another, moving a vertex from the larger part to the smaller part converts many missing within-part pairs into present cross-part edges. Repeating this balancing step can only increase the edge count until all part sizes differ by at most one.
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\):
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.
The forbidden graph's chromatic number sets the leading density threshold
For non-bipartite forbidden graphs, Erdős–Stone says the detailed shape of \(H\) disappears from the leading term: asymptotically, only \(\chi(H)\) matters. A graph that needs more colors can be avoided at a higher density before it becomes unavoidable.
Connection back to coloring: the number of color classes required by the forbidden graph determines the balanced multipartite density that can still avoid it.
Part 19 Mental Model
How large before order is unavoidable?
The first unavoidable size.
Show some good object exists by averaging over random ones.
How dense can we be while avoiding H?
Balanced multipartite graphs are densest clique-avoiders.
Asymptotically, χ(H) controls the density threshold.
Real-World Applications
Communication Network Design & Combinatorial Designs
Extremal graph theory directly informs the design of communication networks and error-correcting codes: Turán-type bounds tell network architects the theoretical maximum connectivity achievable under constraints that forbid certain costly or fragile substructures, while Ramsey-theoretic guarantees are used in distributed computing to prove that certain coordination structures (like guaranteed cliques of mutually-synchronized nodes) are unavoidable once a network grows past a calculable size — turning "surely this won't happen" into a provable certainty engineers must design around.
Exercises
- 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.
- 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.
- 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.
- 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.
Next in the Series
In Part 20: Probabilistic, Random & Spectral Graph Theory, we'll explore the Erdős–Rényi random graph model, the probabilistic method in action, and how a graph's eigenvalues reveal its structure.