Turán-Type Problems

Turán-type problems ask for the maximum number of edges in a graph or hypergraph that avoids a given substructure. These problems form one of the central pillars of extremal combinatorics and have deep connections to algebra, probability, and topology.

Graph Turán Theory

Definition4.5Turán Number

For a graph $H$ , the Turán number $\operatorname{ex}(n, H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain $H$ as a subgraph. A graph achieving this maximum is called an extremal graph for $H$ .

Definition4.6Turán Graph

The Turán graph $T(n, r)$ is the complete $r$ -partite graph on $n$ vertices where the part sizes differ by at most one. Specifically, if $n = qr + s$ with $0 \leq s < r$ , then $T(n,r)$ has $s$ parts of size $q+1$ and $r - s$ parts of size $q$ .

The number of edges in $T(n,r)$ is $t(n,r) = \binom{n}{2} - \sum_{i=1}^{r}\binom{n_i}{2} = \left(1 - \frac{1}{r}\right)\frac{n^2}{2} + O(n)$ where $n_1, \ldots, n_r$ are the part sizes.

Density and Limits

Definition4.7Edge Density and Turán Density

The Turán density of a graph $H$ is $\pi(H) = \lim_{n \to \infty} \frac{\operatorname{ex}(n, H)}{\binom{n}{2}}.$ By the Erdos-Stone theorem, this limit always exists and equals $1 - \frac{1}{\chi(H) - 1}$ , where $\chi(H)$ is the chromatic number of $H$ .

ExampleTriangle-Free Graphs

For $H = K_3$ (the triangle), $\chi(K_3) = 3$ , so $\pi(K_3) = 1 - \frac{1}{2} = \frac{1}{2}$ . The extremal graph is $T(n, 2)$ , the complete bipartite graph with balanced parts, having $\lfloor n^2/4 \rfloor$ edges. This is the content of the Mantel theorem (1907).

RemarkSupersaturation

Once the number of edges exceeds $\operatorname{ex}(n, H)$ , the graph must contain not just one copy of $H$ but many. The supersaturation phenomenon states that for $\varepsilon > 0$ , if $|E(G)| \geq (\pi(H) + \varepsilon)\binom{n}{2}$ , then $G$ contains at least $c \cdot n^{|V(H)|}$ copies of $H$ , where $c = c(\varepsilon, H) > 0$ .

Hypergraph Turán Problems

Definition4.8Hypergraph Turán Number

For a $k$ -uniform hypergraph $H$ , the Turán number $\operatorname{ex}_k(n, H)$ is the maximum number of edges in a $k$ -uniform hypergraph on $n$ vertices not containing $H$ as a subhypergraph. The Turán density is $\pi_k(H) = \lim_{n \to \infty} \frac{\operatorname{ex}_k(n, H)}{\binom{n}{k}}.$

Unlike the graph case, determining $\pi_k(H)$ for specific $k$ -uniform hypergraphs with $k \geq 3$ remains one of the major open problems in combinatorics. Even $\pi_3(K_4^{(3)})$ is unknown, where $K_4^{(3)}$ is the complete 3-uniform hypergraph on 4 vertices.

ExampleFano Plane

The Fano plane is the unique $(7,3,1)$ -design and has 7 hyperedges on 7 vertices. De Caen and Furedi showed that $\pi_3(\text{Fano}) = 3/4$ , and the extremal hypergraph is the balanced complete bipartite 3-uniform hypergraph.