- Atlas
- Mathematics
- Extremal Combinatorics
Extremal Combinatorics
Extremal combinatorics asks a deceptively simple kind of question: among all finite structures of a given size that avoid some forbidden pattern, how large can one be, and what does a largest example look like?
10 frameworks, from 1928 to today · Combinatorics · Mathematics
- Extremal Set Theory 1928-Present
- Ramsey Theory 1930-Present
- Extremal Graph Theory 1941-Present
- Probabilistic Method 1947-Present
- Extremal Coding and Design Theory 1948-Present
- Stability Theory 1966-Present
- Linear Algebra Method 1970-Present
- Regularity Method 1975-Present
- Flag algebra 2007-Present
- Container Method 2011-Present
Overview
Extremal combinatorics asks a deceptively simple kind of question: among all finite structures of a given size that avoid some forbidden pattern, how large can one be, and what does a largest example look like1? How many edges can a graph on $n$ vertices have without containing a triangle2? How many subsets of an $n$-element set can you choose without two of them being nested1? How many colours are needed to guarantee a monochromatic triangle in every colouring of a large complete graph3? These questions are easy to state and often hard to answer, and the answers tend to come with a bonus: a description of the structures that achieve the bound, which usually reveals something structural about the whole class.
What is at stake is the boundary between the possible and the impossible in discrete mathematics. Extremal results are the load-bearing walls of combinatorics: they tell algorithm designers when a pattern must appear, they give number theorists and computer scientists quantitative guarantees, and they force the development of techniques—random construction, algebraic linear algebra, regularity, containers—that then spread across the field. The history of extremal combinatorics is largely the history of those techniques.
Beginnings in set theory and the first extremal theorem
The oldest strand is extremal set theory: questions about families of subsets. A family is intersecting if any two of its members share an element; the natural question is how large such a family can be4. The answer, for subsets of an $n$-element set, is that the largest intersecting family has size $2^{n-1}$—take all sets containing a fixed element. This is often called the Erdős–Ko–Rado theorem in its uniform form, but the unrestricted statement is older and elementary. The uniform version, proved by Paul Erdős, Chao Ko, and Richard Rado in 1961, asks for the largest family of $k$-element subsets any two of which intersect, and answers $\\binom{n-1}{k-1}$ for $n \\ge 2k$, again achieved by fixing one element. The proof introduced a technique—shifting, or compression—that replaces a family by a rearranged one with no smaller size and more structure, and shifting remains a standard tool.
A second foundational result is Sperner's theorem of 1928: the largest family of subsets of an $n$-set in which no set contains another (an antichain) has size $\\binom{n}{\\lfloor n/2 \\rfloor}$, the middle layer. Sperner's proof used a clever counting argument with chains; later proofs by Lubell, Meshalkin, and others gave the LYM inequality, a weighted counting identity that has become a template for many extremal set results. These early theorems established the pattern that would recur for a century: a sharp bound, an extremal example with obvious symmetry, and a proof method that generalizes.
Graph theory's founding extremal problem
The birth of extremal graph theory is usually dated to a 1941 paper of Paul Turán25. Turán asked: what is the maximum number of edges in a graph on $n$ vertices that contains no complete graph $Kr$ on $r$ vertices5? His answer, the Turán graph, is the complete $(r-1)$-partite graph with parts as equal as possible, and its edge count is the Turán number $t{r-1}(n)$5. The result is a paradigm: the extremal object is a complete multipartite graph, and the bound is exact for every $n$. Turán's motivation was partly a problem in a mathematical competition, but the theorem opened a field.
The general problem—given a forbidden graph $H$, find the maximum number of edges in an $n$-vertex graph with no copy of $H$, written $\\mathrm{ex}(n,H)$—became central5. For bipartite $H$ the problem is much harder and remains largely open; the Kővári–Sós–Turán theorem of the 1950s gave the first general upper bound for complete bipartite forbidden graphs, using a double-counting argument over pairs of vertices. This split—exact answers for non-bipartite forbidden graphs, asymptotic and still-incomplete answers for bipartite ones—has organized the subject ever since.
Ramsey theory: order out of chaos
Ramsey theory is the branch concerned with the inevitability of patterns in large structures6. Frank Ramsey's 1930 theorem states that for any $r$ and $k$ there is an $N$ such that every colouring of the edges of $KN$ with $r$ colours contains a monochromatic $Kk$. The finite version was not Ramsey's main concern—he proved an infinite statement—but the finite statement became the engine of a field.
The central quantity is the Ramsey number $R(k)$, the least $N$ forcing a monochromatic $K_k$ in any two-colouring3. Erdős and George Szekeres gave an upper bound in 1935, and Erdős's 1947 lower bound—a random colouring argument—is often cited as the birth of the probabilistic method. The gap between the bounds, roughly $\\sqrt{2}^{k}$ versus $2^{k/2}$, has narrowed only slowly; the exact values of $R(k)$ are known only for small $k$. Ramsey theory grew into a large area with its own vocabulary: Ramsey-type results assert that some pattern must appear, and the extremal question is how large the host structure must be.
The probabilistic method
The probabilistic method, developed principally by Erdős from the late 1940s onward, is the idea of proving that an object with a desired property exists by showing that a randomly chosen object has the property with positive probability. Its first famous use is the Ramsey lower bound: colour each edge of $KN$ independently red or blue; the expected number of monochromatic $Kk$'s is $\\binom{N}{k}2^{1-\\binom{k}{2}}$, which is less than 1 for $N$ around $2^{k/2}$, so some colouring has none. The method's power is that it produces existence proofs without constructing anything.
The method matured through the 1960s and 1970s with tools for handling dependence. The Lovász local lemma, proved by Erdős and László Lovász in 1975, gives a criterion under which a collection of bad events, each depending on only a few others, can all be avoided simultaneously7. It became a workhorse for existence results in graph colouring, scheduling, and combinatorics generally. The probabilistic method also supplied the alteration technique—choose randomly, then delete the few bad pieces—and the second moment method for showing that a random structure has a property with high probability. These tools turned extremal combinatorics from a collection of clever arguments into a discipline with reusable machinery.
Stability and the structure of extremal examples
A recurring phenomenon is that near-extremal objects look almost like the extremal ones. Stability theory makes this precise: if a graph has almost as many edges as the Turán bound and no $K_r$, then it can be made $(r-1)$-partite by deleting few edges. Early stability results go back to Erdős and Simonovits in the 1960s and 1970s, and the idea became a standard step in proofs: first show the extremal example is close to a known structure, then refine.
Stability is closely tied to the regularity method. Endre Szemerédi's regularity lemma, proved in the 1970s in work on arithmetic progressions, says that every large graph can be partitioned into a bounded number of parts so that the edges between most pairs of parts behave almost randomly8. This structural approximation lets extremal problems be reduced to finite problems on a small "reduced graph." The lemma was initially seen as a tool for dense graphs and was applied to extremal questions—counting copies of a fixed graph, proving removal lemmas—through the 1990s and 2000s. Its limitation to dense graphs was a known obstacle; the development of sparse regularity lemmas for graphs of bounded degree came later and extended the method's reach.
Algebraic and linear-algebraic methods
A parallel tradition attacks extremal problems with linear algebra. The idea is to associate to a combinatorial structure a matrix or vector space and use rank or dimension arguments. The linear algebra method in extremal set theory—often associated with the work of László Babai, Péter Frankl, and others from the 1970s and 1980s—proves bounds on families of sets by assigning vectors and bounding their independence. A classic example is the bound on oddtown or on families with restricted intersections, where a polynomial or matrix argument gives a sharp answer that combinatorial counting cannot easily reach.
This algebraic strand connects extremal combinatorics to design theory and coding theory. Extremal questions about block designs—how many blocks a design can have under intersection constraints—and about error-correcting codes—how large a code can be with a given minimum distance—are close cousins of the graph and set problems, and the Plotkin bound and Hamming bound in coding theory are extremal statements in the same spirit. The cross-fertilization has been steady: design-theoretic constructions supply extremal examples, and extremal bounds constrain what designs and codes can exist.
Flag algebras and the computer-assisted turn
By the 1990s many small extremal problems remained open because the case analysis was too large for hand proofs. Alexander Razborov's flag algebras, introduced around 2007, gave a systematic way to generate and combine inequalities among densities of small subgraphs, turning extremal problems into semidefinite or linear programs that a computer can solve9. The method produced new exact results and, importantly, certified proofs that could in principle be checked. It is a descendant of the earlier Kruskal–Katona and compression traditions in set theory and of the linear-algebra method, but its automation was new.
The flag-algebra approach exemplifies a broader shift: extremal combinatorics increasingly uses computation not just to conjecture but to verify. This has raised questions about the nature of proof and the role of human insight, questions the field is still working through.
Containers and the sparse regime
The container method, developed by József Balogh, Robert Morris, and Wojciech Samotij, and independently by David Saxton and Andrew Thomason, in the early 2010s, addresses a limitation of the probabilistic method: it often gives existence but not counting. The container method shows that the independent sets of a graph—or more generally, the objects avoiding a forbidden pattern—can be covered by a small number of "containers," each of which is a simple structured set. This yields both counting results and sharper extremal bounds, and it has been especially effective for sparse graphs and for hypergraph problems where earlier methods stalled. It descends from the regularity method and from the independence-polynomial tradition, and it is now a standard tool.
The present
Today extremal combinatorics is a large, fast-moving field with several active fronts. The dense-graph theory built on Turán's theorem and the regularity lemma is mature but still produces new results, especially through flag algebras and stability refinements. The sparse regime—bounded-degree graphs, hypergraphs, and the container method—is where much current energy lies, driven by connections to random graphs, additive combinatorics, and theoretical computer science. Ramsey theory continues to chip away at the gap between upper and lower bounds, with recent progress on diagonal Ramsey numbers using novel combinatorial and computational ideas. Extremal set theory remains active through shifting, algebraic methods, and connections to coding and design theory.
The open questions are the old ones in new dress: exact Turán numbers for bipartite graphs, the true growth rate of Ramsey numbers, the limits of the container method in hypergraphs, and whether flag-algebra computations can be made to scale to the problems that still resist hand proof. What unites the field is still the original question—how large can a structure be before a pattern is forced—and the conviction, borne out repeatedly over a century, that answering it teaches you how discrete structures are put together.
References
- Extremal combinatorics, Wikipedia
- Extremal graph theory (History), Wikipedia
- Ramsey's theorem, Wikipedia
- Erdős–Ko–Rado theorem, Wikipedia
- Turán's theorem, Wikipedia
- Ramsey theory, Wikipedia
- Lovász local lemma, Wikipedia
- Szemerédi regularity lemma, Wikipedia
- Flag algebra, Wikipedia
The frameworks of Extremal Combinatorics
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1928-Present
Extremal Set Theory
How large can a family of sets be without a forbidden pattern?
- 1930-Present
- 1941-Present
Extremal Graph Theory
How many edges can a graph have without a forbidden subgraph?
- 1947-Present
- 1948-Present
Extremal Coding and Design Theory
How large can a code or design be under distance constraints?
- 1966-Present
- 1970-Present
Linear Algebra Method
How can linear algebra bound combinatorial families?
- 1975-Present
- 2007-Present
- 2011-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Probabilistic Method influenced by Ramsey Theory
Erdős's 1947 lower bound for Ramsey numbers was obtained by colouring edges at random and counting expected monochromatic copies. This argument is the founding use of the probabilistic method.
Carried by Paul Erdős.
Stability Theory grew out of Extremal Graph Theory
Stability theory grew directly out of Turán-type extremal graph problems: it asks what near-extremal graphs without a forbidden subgraph look like. Early stability results by Erdős and Simonovits refined the Turán bound into a structural statement.
Carried by Paul Erdős; Miklós Simonovits.
Linear Algebra Method influenced by Extremal Set Theory
The linear algebra method in extremal set theory attacked the same family-of-sets questions as Sperner and Erdős–Ko–Rado, replacing counting by rank and dimension arguments. Babai, Frankl and others applied it to intersection and oddtown-type problems.
Carried by László Babai; Péter Frankl.
Regularity Method influenced by Extremal Graph Theory
Szemerédi's regularity lemma was applied through the 1980s and 1990s to extremal graph questions, notably counting copies of a fixed graph and proving removal lemmas. The reduced-graph technique became a standard tool for extremal graph theory.
Carried by Endre Szemerédi.
Flag algebra grew out of Extremal Graph Theory
Flag algebras were introduced by Razborov as a systematic way to compute bounds for extremal graph and hypergraph problems, generalizing earlier finite-flag counting arguments. The method answers the same Turán-type questions with semidefinite-style optimization.
Carried by Alexander Razborov.
Container Method influenced by Probabilistic Method
The container method combines probabilistic and hypergraph techniques to bound the number of independent sets and forbidden configurations. It grew out of the probabilistic tradition of Erdős and the hypergraph methods developed in that line.
Carried by David Saxton; Andrew Thomason.
Beyond the field
Where Extremal Combinatorics's ideas came from in other fields, and what they led to there: the strongest 12 of 40 links.
Extremal Graph Theory influenced by Graph Theory in Combinatorics
Turán's theorem and the extremal problems that followed were formulated entirely within graph theory, taking the graph as the object whose edge count is maximised under forbidden subgraphs.
Carried by Paul Turán.
Probabilistic Method led to Lovász Local Lemma in Probabilistic Combinatorics
The local lemma was created to handle extremal-combinatorics problems where the probabilistic method's naive union bound failed because bad events were numerous but weakly dependent.
Carried by László Lovász; Paul Erdős.
Probabilistic Method led to Random graph in Probabilistic Combinatorics
The random graph is the central probabilistic-method device in extremal combinatorics, introduced by Erdős to settle extremal existence questions through random constructions.
Carried by Paul Erdős.
Probabilistic Method influenced Color Coding in Parameterized Algorithms
Color coding is a derandomizable application of the probabilistic method: random colorings make a solution colorful with nonzero probability, and the method guarantees existence of such colorings. The technique's analysis is a direct use of probabilistic existence arguments.
Regularity Method influenced Graph Limits in Combinatorics
Szemerédi's regularity lemma, and its later counting and sampling versions, is the direct technical ancestor of graph limit theory: the limit object was constructed to make the lemma's partition picture exact. Lovász and Szegedy built graphon theory on regularity-type convergence.
Carried by Endre Szemerédi; László Lovász; Balázs Szegedy.
Regularity Method grew out of Extremal graph theory in Graph Theory
The regularity method was developed within extremal graph theory as a tool for proving density theorems, most famously Szemeredi's theorem and the Erdos-Stone-Simonovits results. It is a branch of extremal graph theory's programme of determining extremal densities.
Carried by Endre Szemerédi.
Flag algebra grew out of Graph Limits in Combinatorics
Flag algebras were introduced by Razborov as a finitary counterpart to graph limits (graphons): the algebra of flags is a dense, finitary version of the limit object, and the method translates extremal problems into semidefinite programmes over this algebra. The theory of graph limits directly shaped flag algebra computations.
Carried by Alexander Razborov; László Lovász.
Extremal Set Theory influenced Extremal graph theory in Graph Theory
Extremal set theory supplied the model and methods for extremal graph theory: forbidding a subgraph is the graph analogue of forbidding a subset pattern, and set-system results guided early graph extremal problems.
Carried by Paul Erdős; Richard Rado.
Extremal Set Theory influenced Container Method in Probabilistic Combinatorics
Container results were first proved for extremal set theory problems such as counting independent sets in hypergraphs and applied to classical set-system questions, building on the extremal set theory tradition of Erdős and others.
Carried by József Balogh; Wojciech Samotij.
Ramsey Theory influenced Probabilistic Method in Combinatorics
Ramsey theory supplied the probabilistic method with one of its first and most famous applications, Erdős's 1947 lower bound for Ramsey numbers obtained by counting random colourings.
Carried by Paul Erdős.
Ramsey Theory influenced Large cardinal in Set Theory
Ramsey theory, founded by Ramsey in 1930, supplied large cardinal theory with combinatorial partition properties; Erdős and Tarski used partition relations to characterise measurable and other large cardinals.
Carried by Frank Ramsey; Paul Erdős; Alfred Tarski.
Ramsey Theory influenced Extremal graph theory in Graph Theory
Ramsey theory supplied the pigeonhole-style existence arguments that extremal graph theory uses, and Ramsey-type questions about unavoidable subgraphs are a strand of the extremal programme.
Carried by Frank P. Ramsey.

Extremal Combinatorics is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Extremal CombinatoricsRelated fields
Fields its ideas are linked to
- Combinatorics 12 links
- Graph Theory 9 links
- Probabilistic Combinatorics 8 links
- Additive Combinatorics 2 links
- Set Theory 2 links
- Parameterized Algorithms 1 link
- Design Theory 1 link
- Enumerative Combinatorics 1 link
- Information Theory 1 link
- Model Theory 1 link
- Measure Theoretic Probability 1 link
- Reliability Fault Tolerance 1 link
More in Combinatorics
- Additive Combinatorics
- Algebraic Combinatorics
- Coding Theory
- Combinatorial Optimization
- Combinatorics
- Design Theory
- Enumerative Combinatorics
- Graph Theory
- Matroid Theory
- Order Theory
- Probabilistic Combinatorics
See where Extremal Combinatorics sits on the Map of Human Knowledge