Extremal Combinatorics

Extremal combinatorics asks a deceptively simple question: how large or small can a combinatorial structure be if it must avoid some forbidden configuration? The field sits at the intersection of combinatorics, graph theory, and probability, producing theorems of striking precision — sharp numerical bounds that reveal the hidden order in discrete systems. From the pigeonhole principle to some of the deepest results of twentieth-century mathematics, extremal combinatorics has become one of the richest and most active areas in all of discrete mathematics.

Ramsey Theory

The starting point for Ramsey theory is an observation that feels almost philosophical: in any sufficiently large system, complete disorder is impossible. No matter how chaotically you color or label the elements of a large enough structure, some organized substructure must emerge. This idea, formalized by the British mathematician Frank Plumpton Ramsey in a 1930 paper on mathematical logic, has grown into an entire branch of combinatorics.

The simplest version is the party problem, or the computation of the Ramsey number $R(m, n)$. This number is defined as the smallest integer $N$ such that any red-blue coloring of the edges of the complete graph $K_N$ must contain either a red $K_m$ or a blue $K_n$. The question is: how big must a party be before it is guaranteed to contain either $m$ mutual friends or $n$ mutual strangers? Ramsey proved that these numbers are always finite — the existence theorem alone was his contribution; computing the actual values turns out to be extraordinarily hard.

The first non-trivial case is $R(3, 3) = 6$. In a group of six people, there must always exist three who all know each other or three who are all strangers. The proof is a clean application of the pigeonhole principle: fix any person $v$; among the five others, by pigeonhole, either at least three are friends of $v$ or at least three are strangers. In either case one can show a monochromatic triangle is forced. Checking that five people are not sufficient requires exhibiting a 2-coloring of $K_5$ with no monochromatic triangle, which is possible using a cycle-based construction. Beyond the small cases, exact values are known only for $R(3, n)$ for a handful of $n$, and the general diagonal numbers $R(n, n)$ remain one of the great open problems in combinatorics. The current state of knowledge places $R(4,4) = 18$ and $R(5,5)$ somewhere between $43$ and $48$.

To prove that $R(m, n)$ is always finite, Ramsey’s original argument gives the recursive upper bound

$R(m, n) \leq R(m-1, n) + R(m, n-1),$

from which one derives $R(m, n) \leq \binom{m+n-2}{m-1}$. For the diagonal numbers this gives $R(n, n) \leq \binom{2n-2}{n-1} \leq 4^n$. The matching lower bound — showing that $R(n, n)$ is at least exponential in $n$ — was established by Paul Erdős in 1947 using the probabilistic method. Color each edge of $K_N$ red or blue independently and uniformly at random. The probability that any fixed set of $n$ vertices spans a monochromatic clique is $2 \cdot 2^{-\binom{n}{2}}$. Since there are $\binom{N}{n}$ such sets, the expected number of monochromatic $n$-cliques is less than one when $N < 2^{n/2}$. This non-constructive argument — existence proven through expectation — launched the entire probabilistic method as a technique in combinatorics, a tool that would prove indispensable for decades to come.

Ramsey theory extends far beyond graphs. Van der Waerden’s theorem (1927) asserts that for any positive integers $r$ and $k$, there is a number $W(r, k)$ such that any $r$-coloring of $\{1, 2, \ldots, W(r,k)\}$ must contain a monochromatic arithmetic progression of length $k$. The infinite version of Ramsey’s theorem, also due to Ramsey, states that for any coloring of all $k$-element subsets of the natural numbers with finitely many colors, there is an infinite monochromatic subset — a set all of whose $k$-element subsets receive the same color. Ramsey theory thus encompasses a family of results with a unified moral: large enough structures are never truly chaotic.

Extremal Graph Theory and Turan’s Theorem

While Ramsey theory asks when an ordered substructure must appear, extremal graph theory asks a more quantitative question: what is the maximum number of edges a graph on $n$ vertices can have without containing a particular subgraph $H$? This quantity is denoted $\mathrm{ex}(n, H)$ and called the Turán number of $H$.

The foundational result is Turán’s theorem, proved by the Hungarian mathematician Pál Turán in 1941 while he was interned in a forced labor camp. The theorem gives a complete answer when the forbidden subgraph is a complete graph $K_r$. The unique $K_r$-free graph on $n$ vertices with the most edges is the Turán graph $T(n, r-1)$, which is the complete $(r-1)$-partite graph with part sizes as equal as possible. The number of edges in $T(n, r-1)$ is

$\mathrm{ex}(n, K_r) = \left(1 - \frac{1}{r-1}\right)\frac{n^2}{2} + O(n),$

and more precisely $\left|E(T(n,r-1))\right| = \left(1 - \frac{1}{r-1}\right)\frac{n^2}{2}$ up to lower-order terms. Turán’s proof combined a clever double-counting argument with an optimization over partitions, and the theorem has since been re-proved in many elegant ways, including a beautiful two-line proof using a probabilistic reweighting technique.

The case $r = 3$ deserves special attention: Turán’s theorem says that a triangle-free graph on $n$ vertices can have at most $n^2/4$ edges, achieved uniquely by the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$. This is Mantel’s theorem, first proved by Willem Mantel in 1907, and it is one of the oldest results in extremal graph theory.

When the forbidden subgraph $H$ is bipartite, Turán numbers behave differently — they grow sub-quadratically. The Kővári-Sós-Turán theorem (1954) addresses the case of the complete bipartite graph $K_{s,t}$ with $s \leq t$. It states that

$\mathrm{ex}(n, K_{s,t}) \leq \frac{1}{2}\left((t-1)^{1/s} n^{2-1/s} + (s-1)n\right).$

This is one of the key tools for bounding edges in graphs that avoid certain dense bipartite subgraphs, with applications throughout incidence geometry and additive combinatorics.

A central modern tool in extremal graph theory is Szemerédi’s regularity lemma, proved by Endre Szemerédi in 1975. It says that the vertex set of any large graph can be partitioned into a bounded number of roughly equal parts such that most pairs of parts behave “pseudorandomly” — the edge density between them is approximately uniform across subsets. Formally, a pair of vertex sets $(A, B)$ is $\varepsilon$-regular if for all $X \subseteq A$ and $Y \subseteq B$ with $|X| \geq \varepsilon|A|$ and $|Y| \geq \varepsilon|B|$, the edge density $d(X, Y)$ satisfies $|d(X, Y) - d(A, B)| \leq \varepsilon$. The lemma guarantees that for any $\varepsilon > 0$, the vertices can be partitioned into at most $M(\varepsilon)$ parts with all but $\varepsilon$ of pairs being regular. Although the bound $M(\varepsilon)$ is a tower function and thus enormous, the lemma is extraordinarily powerful as a structural tool, enabling the so-called graph removal lemma and serving as the engine behind Szemerédi’s theorem on arithmetic progressions.

Turán density $\pi(H) = \lim_{n \to \infty} \mathrm{ex}(n, H) / \binom{n}{2}$ captures the asymptotic fraction of edges a graph can have while remaining $H$-free. For complete graphs $K_r$, Turán’s theorem gives $\pi(K_r) = 1 - 1/(r-1)$. For bipartite graphs $H$, the Kővári-Sós-Turán theorem implies $\pi(H) = 0$. Computing or even estimating Turán density for specific hypergraphs remains one of the hardest open problems in combinatorics.

Extremal Set Theory

Extremal set theory asks analogous questions for families of sets rather than graphs: given a constraint on how sets in a family may intersect (or avoid intersecting), how large can the family be? This field was shaped in large part by the extraordinary insight and prolific output of Paul Erdős, who collaborated with researchers across the world over more than six decades.

The first landmark result is Sperner’s theorem (1928), proved by the German mathematician Emanuel Sperner. A family $\mathcal{F}$ of subsets of $[n] = \{1, 2, \ldots, n\}$ is an antichain (also called a Sperner family) if no set in $\mathcal{F}$ is a subset of another. Sperner proved that the maximum size of an antichain is $\binom{n}{\lfloor n/2 \rfloor}$, achieved by taking all subsets of size $\lfloor n/2 \rfloor$. The proof uses the beautiful LYM inequality (named after Lubell, Yamamoto, and Meshalkin, who found it independently in the 1950s and 60s): for any antichain $\mathcal{F}$,

$\sum_{F \in \mathcal{F}} \frac{1}{\binom{n}{|F|}} \leq 1.$

This inequality follows from counting maximal chains in the Boolean lattice $2^{[n]}$. Each maximal chain has $n!$ orderings, there are $n!$ maximal chains in total (corresponding to permutations of $[n]$), and a chain can pass through at most one member of an antichain. The bound on antichain size then follows immediately from the LYM inequality by noting that $1/\binom{n}{|F|} \geq 1/\binom{n}{\lfloor n/2 \rfloor}$.

The Erdős-Ko-Rado theorem (1961), proved by Erdős, Ko, and Rado after more than twenty years of effort on the problem, addresses intersecting families — collections of $k$-element subsets of $[n]$ such that every two sets in the family share at least one element. The theorem states that if $n \geq 2k$, then any such family has size at most $\binom{n-1}{k-1}$. Equality holds for the family of all $k$-element subsets containing a fixed element, called a star. The condition $n \geq 2k$ is necessary: when $n < 2k$ any two $k$-subsets of $[n]$ automatically intersect (by pigeonhole), and the entire family of all $\binom{n}{k}$ subsets is intersecting.

The original proof by Erdős, Ko, and Rado used a beautiful cyclic argument: arrange the elements of $[n]$ in a random cyclic order, and count how many members of $\mathcal{F}$ can form consecutive arcs of length $k$ in that order. Each cyclic order contributes at most $k$ arcs in $\mathcal{F}$, and the averaging argument gives the bound. A later proof by Katona (1972) is even more elegant and is widely regarded as one of the most beautiful arguments in combinatorics. The EKR theorem has spawned an enormous industry of intersection theorems: versions for $t$-intersecting families (where any two sets share at least $t$ elements), versions for vector spaces and permutations, and analytical generalizations using spectral methods.

The concept of shifting (also called compression) is the key technical tool underlying many extremal set theory arguments. Given a family $\mathcal{F}$ of sets and indices $i < j$, the shift operation replaces each set $F \in \mathcal{F}$ containing $j$ but not $i$ with $(F \setminus \{j\}) \cup \{i\}$, provided this new set is not already in $\mathcal{F}$. Shifting reduces the family toward the “initial segment” of the lexicographic order without decreasing its size or destroying the intersection property, allowing one to assume without loss of generality that the extremal family has a particularly clean structure.

Fisher’s inequality, another landmark of this area, states that if $\mathcal{F}$ is a family of subsets of $[n]$ such that every two distinct sets in $\mathcal{F}$ have the same intersection size $\lambda$, and all sets in $\mathcal{F}$ have the same size $k \neq \lambda$, then $|\mathcal{F}| \leq n$. The proof is a linear algebra argument: consider the incidence vectors of the sets as vectors in $\mathbb{R}^n$ and show they are linearly independent.

Forbidden Substructures and Stability

Once we know the maximum size of a combinatorial structure that avoids some forbidden configuration, the next natural question is: what does the extremal structure look like? And more subtly, are all near-extremal structures structurally close to the actual extremal ones? The theory that addresses this is called stability theory in extremal combinatorics.

The prototype is the stability version of Turán’s theorem, due to Erdős and Simonovits. The Erdős-Simonovits stability theorem says that if $G$ is a $K_r$-free graph on $n$ vertices with $(1 - o(1))\mathrm{ex}(n, K_r)$ edges, then $G$ can be made into the Turán graph $T(n, r-1)$ by adding and deleting $o(n^2)$ edges. In other words, any graph that is nearly as dense as possible while remaining $K_r$-free must be nearly $(r-1)$-partite. The proof uses the regularity lemma: apply Szemerédi’s lemma to $G$, observe that most pairs of parts are regular with density close to $1 - 1/(r-1)$, then use the extremality to deduce the approximate multipartite structure.

Stability results transform qualitative existence theorems into structural characterizations, and they have been obtained for many other forbidden subgraphs and hypergraphs. The general pattern: an extremal configuration is unique (or belongs to a small explicit class), and near-extremal configurations are structurally close to it. This is analogous to stability results in functional analysis, where the only functions achieving equality in an inequality are exactly the functions one expects, and nearby functions have a similar form.

The sunflower lemma, proved by Erdős and Rado in 1960, is another fundamental result about forbidden substructures in set families. A sunflower (or $\Delta$-system) with $p$ petals is a family of $p$ sets $S_1, \ldots, S_p$ such that all pairwise intersections equal a common core $S_i \cap S_j = Y$ for $i \neq j$. The sunflower lemma states: if $\mathcal{F}$ is a family of more than $(p-1)^k \cdot k!$ sets each of size $k$, then $\mathcal{F}$ contains a sunflower with $p$ petals. Equivalently, any sufficiently large uniform set family must contain a structured “flower.” The lemma is a powerful tool in combinatorics, complexity theory, and the theory of algorithms, and the question of whether the factorial factor $k!$ in the bound can be replaced by something smaller is the sunflower conjecture — one of the major open problems in combinatorics, attracting renewed attention from computer scientists in recent years due to its implications for circuit lower bounds.

For hypergraph Turán problems, almost nothing is known. The hypergraph Turán density $\pi(H)$ for a $k$-uniform hypergraph $H$ is defined analogously to the graph case, but determining even a single value for $k \geq 3$ and a non-trivial $H$ is open in most cases. Turán himself conjectured in 1941 that $\pi(K_4^{(3)}) = 5/9$, where $K_4^{(3)}$ is the complete 3-uniform hypergraph on 4 vertices (i.e., all $\binom{4}{3} = 4$ triples). Despite enormous effort by many researchers over eight decades, this conjecture remains open. The difficulty of hypergraph Turán problems reflects a genuine gap in our understanding: the techniques that work beautifully for graphs — the regularity lemma, stability arguments, algebraic methods — do not transfer cleanly to the hypergraph setting.

The flag algebra method, introduced by Alexander Razborov in 2007, represents the most significant methodological advance in extremal combinatorics in many years. The idea is to express extremal inequalities as positive semidefinite conditions on algebras of “typed” combinatorial objects, then use semidefinite programming to find certificates for those inequalities. The method has resolved a number of previously intractable problems, including sharp bounds on hypergraph Turán densities in special cases and new results in Ramsey multiplicity. It represents a striking confluence of combinatorics, linear algebra, and optimization, and it continues to be an active area of development. Flag algebras, together with the classical regularity method, stability theory, and the probabilistic method, constitute the modern toolkit with which extremal combinatorics confronts its hardest open questions — questions that lie at the boundary between what is known and what can be imagined.