Loading field map
Extremal combinatorics is the branch of combinatorics concerned with determining the maximum or minimum possible size of a collection of discrete objects subject to a set of constraints. Its central questions take the form: given a family of finite sets, graphs, sequences, or other discrete structures, and a rule that forbids certain configurations, how large can the family be before it must contain a forbidden configuration? The field seeks exact answers where possible, asymptotic answers where exact ones are intractable, and structural descriptions of the near-extremal objects that achieve or approach the bounds.
The prototypical problem in extremal combinatorics is the Turán problem for graphs. Given a fixed graph H, what is the maximum number of edges in an n-vertex graph that contains no copy of H as a subgraph? This quantity is denoted ex(n, H). The classical result, due to Pál Turán in 1941, answers the question when H is a complete graph K{r+1}: the extremal graph is the complete r-partite graph with parts as equal as possible, now called the Turán graph T{r}(n). The number of edges in this graph is asymptotically (1 − 1/r)n²/2. This single result established a template for the field: identify the extremal configuration, prove that no larger configuration exists, and then characterize all configurations that come close to the bound.
The Turán problem generalizes in many directions. One can forbid multiple graphs simultaneously, ask about induced subgraphs rather than arbitrary subgraphs, or replace graphs with hypergraphs, where the edges are sets of size k > 2. Hypergraph extremal problems are dramatically harder; even the analogue of Turán's theorem for complete 3-uniform hypergraphs remains unsolved in general, and the asymptotic density of the extremal configuration is known only for a limited class of hypergraphs.
A second fundamental problem type concerns set systems. The Erdős–Ko–Rado theorem, proved in 1961, asks: how large can a family of k-element subsets of an n-element set be, if any two sets in the family must intersect? The answer is that for n ≥ 2k, the maximum is achieved by taking all k-sets containing a fixed element, giving a family of size C(n−1, k−1). This result spawned an entire subfield of extremal set theory, with variations involving pairwise disjointness, multiple intersections, or restrictions on the intersection sizes.
A third major direction concerns sequences and order. The Erdős–Szekeres theorem, from 1935, states that any sequence of (r−1)(s−1) + 1 distinct real numbers contains either an increasing subsequence of length r or a decreasing subsequence of length s. This result, which predates the formalization of extremal combinatorics, exemplifies the field's concern with unavoidable patterns in large structures. Related problems include the study of Davenport–Schinzel sequences, which arise in computational geometry and concern sequences that avoid alternating patterns.
The roots of extremal combinatorics lie in the early twentieth century, when mathematicians began asking quantitative questions about unavoidable patterns. The Erdős–Szekeres theorem and the work of Richard Rado on partition regularity were early contributions, but the field crystallized as a distinct discipline through the collaboration of Paul Erdős and Turán in the 1940s. Turán's theorem provided the first major extremal result, and Erdős's subsequent work, often in collaboration with others, established the field's characteristic style: conjecture-driven, asymptotic in nature, and deeply connected to probability and algebra.
The 1960s and 1970s saw the development of the probabilistic method, pioneered by Erdős. This technique proves the existence of large structures with desired properties by showing that a random structure has a positive probability of satisfying them. The probabilistic method transformed extremal combinatorics by providing a way to establish lower bounds that were previously inaccessible. For example, Erdős used it to show that for any k, there exist graphs with arbitrarily large girth (length of the shortest cycle) and arbitrarily high chromatic number, a result that contradicted the intuition that high chromatic number forces short cycles.
The 1970s also brought the regularity lemma, introduced by Endre Szemerédi in his proof that dense subsets of the integers contain arbitrarily long arithmetic progressions. The lemma states that every sufficiently large graph can be partitioned into a bounded number of parts such that the edges between most pairs of parts behave pseudorandomly. This decomposition tool became central to extremal graph theory, enabling proofs of the Erdős–Stone theorem, which extends Turán's theorem to arbitrary forbidden subgraphs, and the stability method, which characterizes near-extremal configurations.
A third major technique, the flag algebra method, was introduced by Alexander Razborov in 2007. This method uses semidefinite programming to produce upper bounds on densities of subgraphs in large graphs. It has resolved several long-standing conjectures, including the exact value of the Turán density of the 3-uniform hypergraph known as K₄⁻, and has become a standard tool for problems where exact extremal configurations are known or conjectured.
The field is organized less by competing schools than by a shared toolkit of methods, each suited to different types of problems. The most important distinction is between problems where the extremal configuration is dense and those where it is sparse.
For dense problems, where the extremal object contains a positive fraction of all possible edges or sets, the regularity lemma and its variants provide a powerful framework. The approach works by approximating a large graph by a small "reduced graph" whose vertices are the parts of the partition and whose edges represent dense connections between parts. Extremal problems then reduce to optimization problems on the reduced graph. The stability method complements this by showing that if a graph is close to extremal, it must be structurally close to the conjectured extremal configuration; this often allows one to prove exact results by first proving an approximate result and then ruling out small perturbations.
For sparse problems, where the extremal configuration contains only a vanishing fraction of possible edges, different techniques are needed. The probabilistic method provides lower bounds by constructing random graphs with the desired properties, often using the Lovász local lemma to handle dependencies. Upper bounds in sparse settings frequently require sophisticated counting arguments or the use of entropy and compression techniques. The field of extremal graph theory for sparse graphs, sometimes called "extremal graph theory for bounded-degree graphs," has developed its own set of tools, including the dependent random choice method and the use of graph limits.
A third approach, the flag algebra method, sits between these extremes. It is most effective for dense problems where the extremal configuration is known or conjectured to be a specific finite structure. The method works by deriving a system of polynomial inequalities that any large graph must satisfy, then using semidefinite programming to find the best possible upper bound. Its strength is its computational power; its limitation is that it produces numerical bounds that must be interpreted carefully, and it does not by itself produce structural descriptions of extremal configurations.
The relationship between these approaches is complementary rather than competitive. The regularity lemma provides structural information but often yields bounds that are far from optimal. The probabilistic method provides existence proofs but not explicit constructions. Flag algebras provide sharp bounds but require the user to guess the extremal configuration. Many of the field's deepest results combine multiple techniques: a typical proof might use the probabilistic method for the lower bound, the regularity lemma for the upper bound, and stability arguments to close the gap.
A distinct thread within extremal combinatorics uses algebraic methods to prove extremal results. The polynomial method, which represents combinatorial objects as roots of polynomials and then uses algebraic properties of the polynomials to derive bounds, has produced several striking results. The most famous is the proof of the cap set problem, which asks for the largest subset of F₃ⁿ containing no three elements in arithmetic progression. In 2016, Jordan Ellenberg and Dion Gijswijt used the polynomial method to show that such sets have size at most (2.756)ⁿ, a dramatic improvement over previous exponential bounds. This result, building on earlier work by Bateman and Katz and by Croot, Lev, and Pach, demonstrated the power of algebraic techniques in a problem that had resisted combinatorial approaches for decades.
Geometric extremal problems form another important subfield. The Erdős–Szekeres "happy ending" problem asks for the smallest number of points in general position in the plane that guarantees a subset of k points in convex position. The exact answer is known only for small k, and the general problem remains open despite extensive effort. Related problems concern the maximum number of unit distances among n points in the plane, a problem where the best known bounds remain far apart, and the study of crossing numbers of graphs, which connects to both geometry and topology.
Contemporary extremal combinatorics is characterized by several active research fronts. The most prominent is the ongoing effort to resolve the Turán density problem for hypergraphs. While the asymptotic density for graphs is completely understood through the Erdős–Stone theorem, the hypergraph case remains largely open. The known results are isolated: exact densities are known for a handful of hypergraphs, and the general problem is considered one of the central open questions in the field.
A second active area concerns extremal problems for random graphs and other random structures. These problems ask for the typical extremal behavior of a random graph, rather than the worst-case behavior that classical extremal combinatorics studies. This direction, initiated by work of Erdős and collaborators in the 1980s, has grown substantially with the development of tools for analyzing random structures.
A third area is the study of extremal problems for permutations, sequences, and other ordered structures. The field of permutation patterns, which asks how many permutations of length n can avoid a given pattern, has connections to both extremal combinatorics and to the theory of partially ordered sets. Similarly, extremal problems for sequences with forbidden subsequences, such as Davenport–Schinzel sequences, have applications in computational geometry and have developed their own sophisticated theory.
The field also maintains deep connections to other areas of mathematics. The regularity lemma has found applications in number theory through Szemerédi's theorem and its generalizations. The probabilistic method connects to theoretical computer science, where it is used to prove the existence of algorithms and to analyze random structures. Flag algebras have been applied to problems in extremal set theory and to the study of quasirandom structures.
A notable feature of the current landscape is the increasing role of computation. Flag algebra calculations are routinely performed with computer assistance, and the resulting bounds are often verified by hand only after the fact. This has led to a debate within the field about the status of computer-assisted proofs, with some mathematicians accepting them as valid and others demanding fully human-verifiable arguments. The debate remains unresolved, but the practical importance of computational methods is undisputed.
The field's open problems range from the very specific to the very general. The Turán density problem for hypergraphs is a specific but central question. The Erdős–Szekeres problem on convex subsets of points is a specific geometric question that has resisted solution for decades. More broadly, the field lacks a general theory that would unify the diverse methods used for different types of extremal problems. The search for such a theory, whether through graph limits, algebraic methods, or some yet-unimagined approach, remains an ongoing aspiration rather than an achieved goal.