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

still a working view ended · each leads to its entry below

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

  1. Extremal combinatorics, Wikipedia
  2. Extremal graph theory (History), Wikipedia
  3. Ramsey's theorem, Wikipedia
  4. Erdős–Ko–Rado theorem, Wikipedia
  5. Turán's theorem, Wikipedia
  6. Ramsey theory, Wikipedia
  7. Lovász local lemma, Wikipedia
  8. Szemerédi regularity lemma, Wikipedia
  9. 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.

  1. 1928-Present

    Extremal Set Theory

    How large can a family of sets be without a forbidden pattern?

    Fly to its tower in Nousfarer

  2. 1930-Present

    Ramsey Theory

    How large must a structure be to force a pattern?

    Fly to its tower in Nousfarer

  3. 1941-Present

    Extremal Graph Theory

    How many edges can a graph have without a forbidden subgraph?

    Fly to its tower in Nousfarer

  4. 1947-Present

    Probabilistic Method

    When does a random object have a desired property?

    Fly to its tower in Nousfarer

  5. 1948-Present

    Extremal Coding and Design Theory

    How large can a code or design be under distance constraints?

    Fly to its tower in Nousfarer

  6. 1966-Present

    Stability Theory

    What do near-extremal structures look like?

    Fly to its tower in Nousfarer

  7. 1970-Present

    Linear Algebra Method

    How can linear algebra bound combinatorial families?

    Fly to its tower in Nousfarer

  8. 1975-Present

    Regularity Method

    How can a large graph be approximated by a small one?

    Fly to its tower in Nousfarer

  9. 2007-Present

    Flag algebra

    How can systematic computation give sharp extremal bounds?

    Fly to its tower in Nousfarer

  10. 2011-Present

    Container Method

    How many structures avoid a forbidden configuration?

    Fly to its tower in Nousfarer

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.

Extremal Set TheoryRamsey TheoryExtremal Graph TheoryProbabilistic MethodExtremal Coding and Design TheoryStability TheoryLinear Algebra MethodRegularity MethodFlag algebraContainer Method

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Combinatorics

Related fields

Fields its ideas are linked to

More in Combinatorics

See where Extremal Combinatorics sits on the Map of Human Knowledge