Extremal combinatorics

Extremal combinatorics determines the largest or smallest size of a discrete structure that can satisfy given constraints, often by proving sharp bounds.

Graph theory: The mathematical study of graphs, which consist of vertices joined by edges. Many extremal questions ask how many edges a graph can contain under a forbidden-pattern constraint.
Probabilistic method: A proof technique that establishes existence by showing a random object has positive probability of desired properties. Random constructions often provide lower bounds for extremal quantities.
Erdős–Stone theorem: A theorem determining the asymptotic edge limit for graphs avoiding a fixed non-bipartite graph. It gives the asymptotic framework behind many forbidden-subgraph edge bounds.
Paul Erdős: A Hungarian mathematician whose work transformed number theory, combinatorics, and probabilistic reasoning. His problems and papers established many of the field's central themes.
Erdős–Hajnal conjecture: A conjecture that every graph excluding a fixed induced subgraph contains a polynomial-size clique or independent set. It asks how strongly one forbidden pattern forces large homogeneous subsets.
Set system: A collection of subsets of a ground set. Extremal set theory bounds the size of families that obey intersection or containment rules.
Double counting: A proof technique that counts the same finite set in two different ways. Comparing two counts yields many elementary extremal inequalities.
Kővári–Sós–Turán theorem: A theorem bounding the number of edges in a graph that avoids a fixed complete bipartite subgraph. It illustrates quantitative bounds for forbidden bipartite patterns.
W. T. Tutte: A British-Canadian mathematician known for foundational work in graph theory and combinatorics. His graph-theoretic work helped shape the structures studied by extremal graph theory.
Zarankiewicz problem: The problem of determining the maximum number of ones in a zero-one matrix avoiding a specified all-ones submatrix. Its unresolved asymptotics test the precision of extremal bounds for forbidden bipartite graphs.

Linked from 9 pages