Contents / Combinatorics / Extremal Graph Theory

Chapter 7

Extremal Graph Theory

The extremal function ex(n,H): Mantel and Turán with proofs and the unique extremal graph, supersaturation and stability, Kővári–Sós–Turán and Erdős–Stone, and the regularity and removal lemmas behind Roth, Szemerédi and Green–Tao.

Introduction

How many edges a graph can carry before a forbidden subgraph is forced: the extremal function, Turán's theorem and its extremal graph, the bipartite and asymptotic theories, and the density theorems of Roth and Szemerédi that grew out of the same question.

7.1The Extremal Function and Mantel's Theorem

Extremal graph theory asks one question in many costumes: how large can a structure be if it avoids something? The structure is a graph, the size is its number of edges, and the thing avoided is a fixed graph $H$ . The whole subject is organised around a single function.

Definition 7.1 (Subgraph containment). A graph $G$ contains $H$ , written $H \subseteq G$ , if some subgraph of $G$ is isomorphic to $H$ ; equivalently, if there is an injection $\varphi : V(H) \to V(G)$ with $\varphi(u)\varphi(v) \in E(G)$ whenever $uv \in E(H)$ . If no such injection exists, $G$ is $H$ -free.

Pitfall. Containment here is not induced containment. The injection must carry edges of $H$ to edges of $G$ , but it is allowed to carry non-edges of $H$ to edges of $G$ as well. So $K_4$ contains $C_4$ (take any four vertices), and " $C_4$ -free" therefore means "no four vertices carry a cycle of length four", not "no four vertices induce exactly a $4$ -cycle". Induced containment is a different and generally harder theory.

Definition 7.2 (The extremal function). For a graph $H$ and an integer $n \ge 1$ , the extremal number (or Turán number) of $H$ is

\mathrm{ex}(n, H) = \max\bigl\{\, e(G) \;:\; |V(G)| = n,\ H \not\subseteq G \,\bigr\},

the largest number of edges an

H

-free graph on

n

labelled vertices can have. A graph attaining the maximum is an extremal graph for

H

, and

\mathrm{EX}(n,H)

denotes the set of all of them.

Two trivial values fix the scale. If $H = K_2$ is a single edge, an $H$ -free graph has no edges at all, so $\mathrm{ex}(n, K_2) = 0$ . If $H$ has more than $n$ vertices then no $n$ -vertex graph can contain it and $\mathrm{ex}(n,H) = \binom{n}{2}$ . Everything interesting happens between these extremes, and the first structural fact is that the density of the extremal graph can only fall as $n$ grows.

Proposition 7.3 (The extremal density is non-increasing). For every graph $H$ and every $n \ge 3$ ,

\frac{\mathrm{ex}(n, H)}{\binom{n}{2}} \;\le\; \frac{\mathrm{ex}(n-1, H)}{\binom{n-1}{2}}.

Consequently the limit

\pi(H) = \lim_{n\to\infty} \mathrm{ex}(n,H)\big/\binom{n}{2}

exists; it is called the Turán density of

H

Proof. Let $G$ be $H$ -free on $n$ vertices with $e(G) = \mathrm{ex}(n,H)$ edges. For each vertex $v$ the graph $G - v$ is again $H$ -free — deleting vertices cannot create a subgraph — and has $n-1$ vertices, so $e(G-v) \le \mathrm{ex}(n-1, H)$ .

Now count the pair $(v, f)$ where $f$ is an edge of $G - v$ . Every edge of $G$ survives the deletion of exactly $n - 2$ of the $n$ vertices, so

\sum_{v \in V(G)} e(G - v) = (n-2)\,e(G) .

Combining,

(n-2)\,e(G) \le n\,\mathrm{ex}(n-1,H)

, i.e.

e(G) \le \tfrac{n}{n-2}\,\mathrm{ex}(n-1,H)

. Since

\binom{n}{2}\big/\binom{n-1}{2} = \tfrac{n}{n-2}

, dividing by

\binom{n}{2}

gives exactly the claimed inequality. A non-increasing sequence bounded below by

0

converges.∎

The limit $\pi(H)$ exists for every $H$ , which is a strong statement given that the exact value of $\mathrm{ex}(n,H)$ is known for only a handful of graphs. The rest of this chapter is largely the story of computing $\pi(H)$ and, where possible, the exact function behind it.

The first genuine theorem of the subject is over a century old and is still the cleanest illustration of the pattern: a construction, a matching upper bound, and a uniqueness statement.

Theorem 7.4 (Mantel's theorem). (Mantel, 1907) Every triangle-free graph on $n$ vertices has at most $\lfloor n^{2}/4 \rfloor$ edges, so

\mathrm{ex}(n, K_3) = \left\lfloor \frac{n^{2}}{4} \right\rfloor .

The bound is attained only by the balanced complete bipartite graph

K_{\lceil n/2\rceil, \lfloor n/2 \rfloor}

Proof. The construction. Split $V$ into parts $A$ , $B$ with $|A| = \lceil n/2\rceil$ , $|B| = \lfloor n/2 \rfloor$ and join every vertex of $A$ to every vertex of $B$ . A triangle would need two of its vertices in the same part, but parts carry no edges, so the graph is triangle-free; it has $\lceil n/2\rceil\lfloor n/2\rfloor = \lfloor n^{2}/4\rfloor$ edges. (For a split into parts of sizes $a$ and $n-a$ the edge count is $a(n-a)$ , a downward parabola in $a$ maximised at $a = n/2$ ; among integers the maximum is at $a = \lceil n/2 \rceil$ .)

The bound. Let $G$ be triangle-free. If $uv \in E(G)$ then $u$ and $v$ have no common neighbour, so $d(u) + d(v) \le n$ . Summing over all edges and grouping by vertex,

\sum_{uv \in E(G)} \bigl(d(u) + d(v)\bigr) = \sum_{v \in V(G)} d(v)^2 ,

because each vertex

v

contributes

d(v)

to the left-hand sum once for each edge at

v

. By Cauchy–Schwarz,

\sum_v d(v)^2 \ge \bigl(\sum_v d(v)\bigr)^2 / n = 4e(G)^2/n

. Therefore

\frac{4\,e(G)^2}{n} \;\le\; \sum_{v} d(v)^2 \;=\; \sum_{uv\in E}\bigl(d(u)+d(v)\bigr) \;\le\; n\,e(G),

and dividing by

4e(G)/n

(assuming

e(G) > 0

) gives

e(G) \le n^{2}/4

. As

e(G)

is an integer,

e(G) \le \lfloor n^{2}/4\rfloor

Uniqueness. Equality forces equality in Cauchy–Schwarz, so all degrees are equal, say to $d$ , and forces $d(u)+d(v) = n$ on every edge, so $d = n/2$ — which already needs $n$ even — and $e(G) = n^{2}/4$ . A triangle-free graph in which adjacent vertices have disjoint neighbourhoods covering all of $V$ is exactly a complete bipartite graph with parts $N(u)$ and $V \setminus N(u)$ . For odd $n$ the count $\lfloor n^{2}/4\rfloor = (n^{2}-1)/4$ is reached by $K_{(n-1)/2,(n+1)/2}$ , and the same argument applied to a maximum-degree vertex identifies it as the only extremal graph. (The general uniqueness statement is proved for all $r$ in Turán's theorem.)∎

A second proof is worth seeing because it generalises in a different direction — it is really a statement about independent sets, and it is the proof that turns into the induction of the next section.

Proof. (Second proof of the bound.) Let $v$ be a vertex of maximum degree $\Delta$ and put $A = N(v)$ , $B = V \setminus A$ . Since $G$ is triangle-free, $A$ is an independent set: two adjacent neighbours of $v$ would close a triangle with $v$ . Hence every edge of $G$ has at least one endpoint in $B$ , and

e(G) \;\le\; \sum_{b \in B} d(b) \;\le\; |B|\,\Delta \;=\; (n-\Delta)\,\Delta \;\le\; \frac{n^{2}}{4},

the last step because

x(n-x) \le n^{2}/4

for all real

x

. Note that

v \in B

, so the bound is not vacuous.∎

Intuition. Both proofs say the same thing from opposite ends. Triangle-freeness is a local scarcity condition — adjacent vertices must have disjoint neighbourhoods — and the only way to satisfy it while keeping degrees high is to split the vertices into two camps and spend every edge crossing between them. The bipartite graph is not merely one good construction among many; it is the unique shape that saturates the local condition everywhere at once.

Example 7.5. Determine $\mathrm{ex}(5, K_3)$ and exhibit the extremal graph, then decide whether $C_5$ is extremal.

Solution. By Mantel's theorem, $\mathrm{ex}(5,K_3) = \lfloor 25/4 \rfloor = 6$ , attained by $K_{2,3}$ , which indeed has $2 \cdot 3 = 6$ edges and is bipartite, hence triangle-free.

The five-cycle $C_5$ is also triangle-free but has only $5$ edges, so it is not extremal — consistent with the uniqueness clause, which says $K_{2,3}$ is the only $6$ -edge triangle-free graph on five vertices.

To see the bound is not improvable downwards, add any edge to $K_{2,3}$ . The new edge joins two vertices of the same part, and every vertex of the other part is adjacent to both, so a triangle appears immediately. Hence every $5$ -vertex graph with $7$ edges contains a triangle.□

Example 7.6. A graph on $n = 100$ vertices has $2600$ edges. Must it contain a triangle? What if it has $2500$ ?

Solution. Here $\lfloor n^{2}/4 \rfloor = \lfloor 10000/4\rfloor = 2500$ . A graph with $2600 > 2500$ edges exceeds the extremal number, so by Mantel's theorem it cannot be triangle-free: it contains a $K_3$ .

With exactly $2500$ edges no conclusion follows — $K_{50,50}$ has $2500$ edges and no triangle. The extremal number is the last value for which a counterexample survives, and the implication "more edges than $\mathrm{ex}(n,H)$ forces $H$ " is sharp by construction.□

Remark. Mantel's theorem also pins down a Turán density: $\pi(K_3) = \lim \lfloor n^{2}/4\rfloor / \binom n2 = \tfrac12$ . Half of all pairs is the ceiling for triangle-freeness, and Turán's theorem will show that forbidding $K_{r+1}$ raises that ceiling to $1 - 1/r$ .

Exercises for §7.1 →

7.2Turán's Theorem and Zykov Symmetrisation

Mantel forbade a triangle; Turán forbade a clique of any size. The answer has exactly the same shape — a complete multipartite graph with balanced parts — and the statement below is the central theorem of the subject.

Definition 7.7 (Turán graph). For $n \ge r \ge 1$ , the Turán graph $T(n,r)$ is the complete $r$ -partite graph on $n$ vertices whose part sizes differ pairwise by at most $1$ : writing $n = qr + s$ with $0 \le s < r$ , it has $s$ parts of size $q+1$ and $r - s$ parts of size $q$ , with every pair of vertices in different parts joined and no edges inside a part. Its edge count is written $t_r(n) = e(T(n,r))$ .

Theorem 7.8 (Turán's theorem). (Turán, 1941) Let $r \ge 1$ and let $G$ be a $K_{r+1}$ -free graph on $n$ vertices. Then

e(G) \;\le\; t_r(n) \;=\; e\bigl(T(n,r)\bigr),

with equality if and only if

G \cong T(n,r)

. Equivalently,

\mathrm{ex}(n, K_{r+1}) = t_r(n)

and

\mathrm{EX}(n,K_{r+1}) = \{T(n,r)\}

That $T(n,r)$ is admissible is immediate and worth isolating, because it is the half of the theorem that needs no work.

Proposition 7.9 (The Turán graph is $K_{r+1}$ -free). $T(n,r)$ contains no $K_{r+1}$ .

Proof. A clique may use at most one vertex from each part, since two vertices in the same part are non-adjacent. There are $r$ parts, so every clique has at most $r$ vertices. (Equivalently: colouring each part with its own colour is a proper $r$ -colouring, and an $r$ -colourable graph contains no $K_{r+1}$ .)∎

The content of the theorem is that nothing else does better. We give a complete proof by Zykov symmetrisation, which is the argument that makes the shape of the extremal graph appear rather than assuming it. The idea: take any extremal graph and show that it can be pushed, without ever losing edges, into a complete multipartite graph.

Definition 7.10 (Duplicating a vertex). Let $G$ be a graph and $u, v$ distinct vertices. To replace $v$ by a copy of $u$ is to delete all edges at $v$ and join $v$ to every vertex of $N(u) \setminus \{v\}$ . The resulting graph $G'$ has $u$ and $v$ non-adjacent with $N(u) = N(v)$ (they are twins), and

e(G') = e(G) - d_G(v) + d_G(u) \quad\text{when } uv \notin E(G).

Lemma 7.11 (Duplication preserves clique number). If $uv \notin E(G)$ and $G'$ is obtained from $G$ by replacing $v$ by a copy of $u$ , then $\omega(G') \le \omega(G)$ ; in particular, if $G$ is $K_{r+1}$ -free then so is $G'$ .

Proof. Let $K$ be a clique of $G'$ . Since $u$ and $v$ are non-adjacent twins in $G'$ , $K$ contains at most one of them. If $v \notin K$ then $K$ is a clique of $G$ as well, because $G$ and $G'$ agree away from $v$ . If $v \in K$ , then $(K \setminus \{v\}) \cup \{u\}$ is a set of the same size; it is a clique of $G'$ because every vertex of $K \setminus\{v\}$ lies in $N_{G'}(v) = N_{G'}(u)$ , and it avoids $v$ , so by the previous case it is a clique of $G$ . Either way $G$ has a clique of size $|K|$ .∎

Proof. (Turán's theorem.) Fix $n$ and $r$ with $n \ge r \ge 1$ and let $G$ be a $K_{r+1}$ -free graph on $n$ vertices with the maximum possible number of edges; such a $G$ exists because there are finitely many graphs on $n$ labelled vertices.

Step 1: non-adjacency is transitive in $G$ . Suppose not. Then there are vertices $u, v, w$ with $uv \notin E$ , $vw \notin E$ and $uw \in E$ .

Case A: $d(v) < d(u)$ . Replace $v$ by a copy of $u$ . By the Duplication preserves clique number lemma the new graph is still $K_{r+1}$ -free, and it has $e(G) - d(v) + d(u) > e(G)$ edges, contradicting maximality. The symmetric case $d(v) < d(w)$ is identical.

Case B: $d(v) \ge d(u)$ and $d(v) \ge d(w)$ . Form $G''$ by replacing both $u$ and $w$ by copies of $v$ . Since $u$ and $w$ are each non-adjacent to $v$ , the lemma applies twice and $G''$ is $K_{r+1}$ -free. (After the first duplication $u$ is a twin of $v$ , so $u$ is still non-adjacent to $v$ and the second duplication is legitimate.) Count the change: deleting the edges at $u$ and at $w$ removes $d(u) + d(w) - 1$ edges, the $-1$ because the edge $uw$ was counted twice; re-attaching $u$ and $w$ as copies of $v$ adds $d(v)$ edges each, and $u$ , $w$ , $v$ are pairwise non-adjacent so nothing is double-counted. Hence

e(G'') = e(G) - \bigl(d(u) + d(w) - 1\bigr) + 2d(v) \;\ge\; e(G) + 1 ,

again contradicting maximality.

So no such triple exists: the relation " $u = v$ or $uv \notin E$ " is reflexive, symmetric and — by Step 1 — transitive, hence an equivalence relation.

Step 2: $G$ is complete multipartite with at most $r$ parts. The equivalence classes of Step 1 are independent sets, and any two vertices in different classes are adjacent; that is precisely the definition of a complete multipartite graph with the classes as parts. If there were $r+1$ or more parts, picking one vertex from each of $r+1$ parts would give a $K_{r+1}$ . So $G$ is complete $k$ -partite for some $k \le r$ .

Step 3: exactly $r$ parts, balanced. Among complete multipartite graphs on $n$ vertices with at most $r$ parts, $G$ maximises edges. If $k < r$ and some part $P$ has $|P| \ge 2$ , split $P$ into two non-empty parts: this adds edges (the pairs inside $P$ that cross the split) and keeps the graph $(k+1)$ -partite with $k + 1 \le r$ parts, contradicting maximality. Since $n \ge r$ , this forces $k = r$ .

Now suppose two parts had sizes $s_i \ge s_j + 2$ . Move one vertex $x$ from the larger part to the smaller. The vertex $x$ loses the $s_j$ edges to the part it joins and gains the $s_i - 1$ edges to the part it left, a net change of $(s_i - 1) - s_j \ge 1 > 0$ , and the graph is still complete $r$ -partite. Again this contradicts maximality, so all part sizes differ by at most $1$ and $G \cong T(n,r)$ .

Every maximiser is therefore isomorphic to $T(n,r)$ , which proves both the bound $e(G) \le t_r(n)$ and the uniqueness of the extremal graph.∎

Figure 7.12. One symmetrisation step, Case B. On the left,

u

and

w

are both non-adjacent to

v

but adjacent to each other;

v

has the largest degree of the three. On the right,

u

and

w

have been rebuilt as copies of

v

: the edge

uw

and the old edges at

u

and

w

are gone, and all three vertices now attach to

N(v)

. The graph stays

K_{r+1}

-free because the three copies are pairwise non-adjacent, and it strictly gains edges whenever

d(v) \ge d(u), d(w)

Intuition. Symmetrisation is a greedy tidying-up. Whenever two non-adjacent vertices have different degrees, the weaker one is wasting its edges, and you may as well give it the stronger one's neighbourhood; since twins are non-adjacent, no new clique can appear. Repeating drives every graph towards the most symmetric object compatible with the constraint, and "complete multipartite with balanced parts" is what maximal symmetry looks like here. The theorem is less about cliques than about the fact that the constraint is preserved by this tidying.

Pitfall. The symmetrisation argument is applied to a graph already known to be extremal, not to an arbitrary graph. Duplication can easily destroy a property you care about other than clique number — connectivity, girth, planarity — and the proof gives no bound on how many steps a real graph would need. It is an argument about the maximiser, not an algorithm.

Example 7.13. Apply Turán's theorem with $r = 3$ on $n = 8$ vertices: what is the largest number of edges in a $K_4$ -free graph, and which graph achieves it?

Solution. The extremal graph is $T(8,3)$ . Writing $8 = 2\cdot 3 + 2$ , the part sizes are $3, 3, 2$ .

Counting edges by pairs of parts: $3\cdot3 + 3\cdot2 + 3\cdot2 = 9 + 6 + 6 = 21$ . So $\mathrm{ex}(8, K_4) = 21$ , out of $\binom 82 = 28$ possible pairs.

Uniqueness is a real constraint: the complete $3$ -partite graph with parts $4,2,2$ is also $K_4$ -free, but has $4\cdot2+4\cdot2+2\cdot2 = 20 < 21$ edges, exactly as the vertex-moving step in the proof predicts — moving one vertex from the part of size $4$ to a part of size $2$ gains $(4-1)-2 = 1$ edge.□

Exercises for §7.2 →

7.3Two Further Proofs: Induction and Weight Shifting

A theorem this central deserves more than one proof, and the alternatives are not decoration: the induction below is the one that generalises to counting cliques, and the weight-shifting proof is the one that turns Turán's theorem into a statement about a continuous optimisation problem, which is how modern flag-algebra methods attack extremal problems.

Both proofs need the exact edge count of the Turán graph only through one recursion.

Lemma 7.14 (Turán recursion). For $n \ge r \ge 1$ ,

t_r(n) = t_r(n-r) + \binom{r}{2} + (r-1)(n-r).

Proof. Delete one vertex from each part of $T(n,r)$ . Because the part sizes differ by at most $1$ , what remains is again balanced, so it is $T(n-r, r)$ and carries $t_r(n-r)$ edges. The $r$ deleted vertices lie in distinct parts, so they are pairwise adjacent and contribute $\binom{r}{2}$ edges among themselves. Finally a deleted vertex $v$ in a part of size $s_i$ is adjacent to every remaining vertex outside its own part, of which there are $(n-r) - (s_i - 1)$ . Summing over the $r$ deleted vertices,

\sum_{i=1}^{r}\bigl((n-r) - s_i + 1\bigr) = r(n-r) - n + r = (n-r)(r-1),

using

\sum_i s_i = n

. Adding the three contributions gives the recursion.∎

Proof. (Turán's theorem by induction on $n$ .) The statement is vacuous for $n < r+1$ , where no $K_{r+1}$ fits and $T(n,r) = K_n$ is complete; this also settles all $n \le r$ as the base case. So let $n > r$ and assume the bound for all smaller vertex counts.

Let $G$ be $K_{r+1}$ -free on $n$ vertices with $e(G)$ maximal. Then $G$ contains a copy of $K_r$ : otherwise $G$ is $K_r$ -free, and adding any missing edge would keep it $K_{r+1}$ -free — a graph with no $K_r$ cannot acquire a $K_{r+1}$ from a single new edge, since every clique through that edge has at most $2 + (r-2) = r$ vertices — contradicting maximality unless $G$ is already complete, which for $n > r$ contains $K_{r+1}$ . Fix such a copy $A$ with $|A| = r$ .

Split the edges of $G$ into three groups: those inside $A$ , those from $A$ to $B = V \setminus A$ , and those inside $B$ .

Inside $A$ there are exactly $\binom{r}{2}$ edges. Each vertex $b \in B$ has at most $r - 1$ neighbours in $A$ : if $b$ were joined to all $r$ vertices of $A$ , then $A \cup \{b\}$ would be a $K_{r+1}$ . So the second group has at most $(n-r)(r-1)$ edges. The graph induced on $B$ is $K_{r+1}$ -free on $n - r$ vertices, so by the induction hypothesis it has at most $t_r(n-r)$ edges. Altogether

e(G) \;\le\; \binom r2 + (n-r)(r-1) + t_r(n-r) \;=\; t_r(n)

by the Turán recursion lemma. Since

T(n,r)

K_{r+1}

-free with exactly

t_r(n)

edges, the bound is attained, and equality above forces every vertex of

B

to have exactly

r-1

neighbours in

A

and

G[B]

to be extremal, from which an easy induction recovers the complete

r

-partite structure.∎

The second proof replaces the discrete problem by a continuous one. Put a weight on each vertex and try to maximise the total weight of the edges.

Definition 7.15 (Lagrangian of a graph). For a graph $G$ on vertex set $\{1,\dots,n\}$ let $\Delta_n = \{x \in \mathbb{R}^n : x_i \ge 0,\ \sum_i x_i = 1\}$ be the standard simplex, and define

f_G(x) = \sum_{ij \in E(G)} x_i x_j .

The maximum

\lambda(G) = \max_{x \in \Delta_n} f_G(x)

is the Lagrangian of

G

; the maximum is attained because

\Delta_n

is compact and

f_G

continuous.

Theorem 7.16 (Motzkin–Straus). (Motzkin and Straus, 1965) For every graph $G$ with clique number $\omega = \omega(G) \ge 1$ ,

\lambda(G) = \frac{1}{2}\left(1 - \frac{1}{\omega}\right).

Proof. Lower bound. Let $S$ be a clique with $|S| = \omega$ and put $x_i = 1/\omega$ for $i \in S$ , $x_i = 0$ otherwise. Then $f_G(x) = \binom{\omega}{2}\omega^{-2} = \tfrac12(1 - 1/\omega)$ .

Upper bound. Among all maximisers $x \in \Delta_n$ of $f_G$ , choose one whose support $S = \{i : x_i > 0\}$ has the fewest elements. We claim $S$ is a clique.

Suppose $i, j \in S$ with $ij \notin E(G)$ . The variable $x_i$ appears in $f_G$ only through the linear term $x_i \sum_{k \sim i} x_k$ , and similarly for $x_j$ ; since $ij$ is not an edge, no term contains both. So for small $\varepsilon$ the shifted point $x^{\varepsilon}$ , obtained from $x$ by replacing $(x_i, x_j)$ with $(x_i + \varepsilon,\, x_j - \varepsilon)$ , satisfies

f_G(x^{\varepsilon}) = f_G(x) + \varepsilon\left( \sum_{k \sim i} x_k - \sum_{k \sim j} x_k \right),

a function of

\varepsilon

that is linear. Because

x

is a maximiser and both signs of small

\varepsilon

are admissible, the coefficient of

\varepsilon

must vanish. But then

f_G

is constant along the entire shift, so we may take

\varepsilon

to the end of its admissible range:

\varepsilon = x_j

empties coordinate

j

, and

\varepsilon = -x_i

empties coordinate

i

. Either lands on another maximiser with one fewer positive coordinate, contradicting the minimality of

|S|

. Hence

S

is a clique, so

|S| \le \omega

Finally, writing $\sigma = \sum_{i \in S} x_i = 1$ ,

f_G(x) = \sum_{\{i,j\} \subseteq S} x_i x_j = \frac{\sigma^{2} - \sum_{i \in S} x_i^{2}}{2} = \frac{1 - \sum_{i\in S} x_i^{2}}{2} \le \frac{1 - 1/|S|}{2} \le \frac{1}{2}\left(1 - \frac 1\omega\right),

where the first inequality is Cauchy–Schwarz (

\sum_{i \in S} x_i^{2} \ge \sigma^{2}/|S|

).∎

Corollary 7.17 (Turán bound from Motzkin–Straus). If $G$ is $K_{r+1}$ -free on $n$ vertices then $e(G) \le \left(1 - \tfrac1r\right)\tfrac{n^{2}}{2}$ .

Proof. Apply $f_G$ to the uniform weighting $x_i = 1/n$ . Then $f_G(x) = e(G)/n^{2}$ , and $\omega(G) \le r$ , so by Motzkin–Straus $e(G)/n^{2} \le \tfrac12(1 - 1/r)$ .∎

Remark. The Motzkin–Straus route gives the clean bound $(1-1/r)n^{2}/2$ , which equals $t_r(n)$ exactly when $r \mid n$ and otherwise overshoots it by $s(r-s)/(2r) < r/8$ , where $s = n \bmod r$ . It therefore proves Turán's theorem asymptotically and exactly in the divisible case, but not the floor-function refinement or the uniqueness clause; those come from the symmetrisation or induction arguments. Trading exactness for a continuous formulation is the usual bargain, and it is what makes the method extend to hypergraphs, where exact extremal graphs are mostly unknown.

Intuition. Think of the weights as dividing one unit of "mass" among the vertices, with $f_G(x)$ the chance that two independently sampled vertices land on an edge. Weight-shifting says the optimum never needs to split mass between two non-adjacent vertices: their contributions do not interact, so all the mass may as well be piled on whichever of the two is better connected. Push that to its conclusion and the optimal mass sits on a single largest clique, spread evenly.

Example 7.18. Let $G$ be the five-cycle $C_5$ . Compute $\lambda(C_5)$ from Motzkin–Straus, and check it against the uniform weighting.

Solution. $C_5$ is triangle-free with at least one edge, so $\omega(C_5) = 2$ and Motzkin–Straus gives $\lambda(C_5) = \tfrac12(1 - \tfrac12) = \tfrac14$ , attained by putting weight $\tfrac12$ on each endpoint of a single edge: $f = \tfrac12\cdot\tfrac12 = \tfrac14$ .

The uniform weighting $x_i = 1/5$ gives $f = 5 \cdot \tfrac{1}{25} = \tfrac15 < \tfrac14$ , so uniform is not optimal here. This is the gap the corollary tolerates: applied to $C_5$ it only yields $e \le (1-\tfrac12)\tfrac{25}{2} = 6.25$ , whereas $e(C_5) = 5$ and $\mathrm{ex}(5,K_3) = 6$ .□

Exercises for §7.3 →

7.4Inside the Turán Graph

The extremal graph deserves its own examination, because most later refinements — stability, supersaturation, the Erdős–Stone theorem — are phrased as statements about how close a graph is to $T(n,r)$ .

Definition 7.19 (Complete multipartite graphs and blow-ups). Given a graph $F$ on vertices $v_1,\dots,v_k$ and positive integers $n_1,\dots,n_k$ , the blow-up $F[n_1,\dots,n_k]$ replaces each $v_i$ by an independent set $V_i$ of size $n_i$ and joins every vertex of $V_i$ to every vertex of $V_j$ whenever $v_iv_j \in E(F)$ . The Turán graph $T(n,r)$ is exactly the balanced blow-up of $K_r$ .

Proposition 7.20 (Exact edge count). Write $n = qr + s$ with $0 \le s < r$ , so $T(n,r)$ has $s$ parts of size $q+1$ and $r-s$ of size $q$ . Then

t_r(n) \;=\; \binom{n}{2} - s\binom{q+1}{2} - (r-s)\binom{q}{2} \;=\; \left(1 - \frac1r\right)\frac{n^{2}}{2} \;-\; \frac{s(r-s)}{2r}.

In particular

t_r(n) \le \left(1 - \tfrac1r\right)\tfrac{n^{2}}{2}

, with equality exactly when

r \mid n

, and

t_2(n) = \lfloor n^{2}/4\rfloor

Proof. The first expression is immediate: $T(n,r)$ has every pair joined except the pairs lying inside a part, and the parts contribute $\binom{q+1}{2}$ or $\binom q2$ missing pairs each.

For the closed form, substitute $q = (n-s)/r$ . The missing pairs total

s\frac{(q+1)q}{2} + (r-s)\frac{q(q-1)}{2} = \frac{q}{2}\bigl(s(q+1) + (r-s)(q-1)\bigr) = \frac q2\bigl(rq - r + 2s\bigr).

With

rq = n - s

this is

\tfrac{q}{2}(n + s - r)

, and

q = (n-s)/r

turns it into

\frac{(n-s)(n+s-r)}{2r} = \frac{n^{2} - s^{2} - r n + rs}{2r} = \frac{n^{2}}{2r} - \frac{n}{2} - \frac{s(s-r)}{2r}.

Subtracting from

\binom n2 = \tfrac{n^{2} - n}{2}

leaves

\tfrac{n^{2}}{2} - \tfrac{n^{2}}{2r} - \tfrac{s(r-s)}{2r}

, which is the claimed form. The correction term

s(r-s)/(2r)

0

precisely when

s = 0

, and for

r = 2

it equals

\tfrac14

when

n

is odd, giving

\tfrac{n^{2}}{4} - \tfrac14 = \lfloor n^{2}/4\rfloor

.∎

Figure 7.21. The Turán graph

T(7,3)

, the extremal

K_4

-free graph on seven vertices. Its parts have sizes

3, 2, 2

(top, lower left, lower right); all

3\cdot2 + 3\cdot 2 + 2\cdot 2 = 16

cross pairs are edges and no pair inside a part is. Any clique picks at most one vertex per part, so the largest is a triangle.

Three structural facts follow at once from the definition, and each is used later.

Proposition 7.22 (Structure of $T(n,r)$ ). Let $n = qr + s$ as above. Then:

The complement of $T(n,r)$ is a disjoint union of $r$ cliques, of sizes $q+1$ (with multiplicity $s$ ) and $q$ (with multiplicity $r-s$ ).
A vertex in a part of size $s_i$ has degree $n - s_i$ , so $T(n,r)$ has only two distinct degrees, $n-q$ and $n-q-1$ , and is regular exactly when $r \mid n$ .
$\chi(T(n,r)) = r$ and $\omega(T(n,r)) = r$ , and $T(n,r)$ is the unique complete $r$ -partite graph on $n$ vertices with the maximum number of edges.

Proof. (1) Two vertices are non-adjacent in $T(n,r)$ exactly when they share a part, so the complement's components are the parts, each complete.

(2) A vertex is joined to everything outside its own part: $n - s_i$ vertices.

(3) Colouring by part is proper, so $\chi \le r$ ; a transversal of the parts is a $K_r$ , so $\omega \ge r$ and $\chi \ge \omega \ge r$ . For the last claim, suppose a complete $r$ -partite graph has parts with $s_i \ge s_j + 2$ . Moving a vertex from part $i$ to part $j$ changes the edge count by $(s_i - 1) - s_j \ge 1 > 0$ , so it was not maximal. Hence all part sizes differ by at most $1$ , and any two such size vectors are permutations of each other.∎

Intuition. The point of balance is a convexity statement. The missing edges are the pairs inside parts, $\sum_i \binom{s_i}{2}$ , and $\binom{x}{2}$ is a convex function, so for a fixed total $\sum_i s_i = n$ the sum of missing edges is smallest when the $s_i$ are as equal as the integers allow. Maximising edges and minimising missing edges are the same problem read from the two ends.

Pitfall. "Complete $r$ -partite" is not enough: $K_{4,2,2}$ and $T(8,3) = K_{3,3,2}$ are both $K_4$ -free complete $3$ -partite graphs on $8$ vertices, but they have $20$ and $21$ edges. Likewise $r$ -partite with fewer than $r$ parts is wasteful — $K_{4,4}$ is $K_4$ -free on $8$ vertices with only $16$ edges. Turán's uniqueness clause is about the exact part sizes and the exact number of parts.

Example 7.23. Compute $t_3(10)$ in three ways: by pairs of parts, by subtraction, and from the closed formula.

Solution. With $n=10$ , $r=3$ : $10 = 3\cdot3 + 1$ , so $q = 3$ , $s = 1$ and the parts are $4,3,3$ .

By pairs of parts: $4\cdot3 + 4\cdot3 + 3\cdot3 = 12 + 12 + 9 = 33$ .

By subtraction: $\binom{10}{2} - \binom 42 - 2\binom32 = 45 - 6 - 6 = 33$ .

By the closed formula: the main term is $\left(1 - \tfrac13\right)\tfrac{10^2}{2} = \tfrac23\cdot 50 = \tfrac{100}{3}$ and the correction is $\tfrac{s(r-s)}{2r} = \tfrac{1\cdot 2}{6} = \tfrac13$ , so $t_3(10) = \tfrac{100}{3} - \tfrac13 = \tfrac{99}{3} = 33$ .

All three agree, so every graph on $10$ vertices with $34$ or more edges contains a $K_4$ .□

Example 7.24. What is the smallest $n$ for which every graph on $n$ vertices with at least $\tfrac{3}{4}\binom n2$ edges contains a $K_4$ ?

Solution. A $K_4$ -free graph can have $t_3(n)$ edges, so the condition fails precisely when $t_3(n) \ge \tfrac34\binom n2$ , i.e. when the Turán graph itself is that dense.

Using $t_3(n) \le \tfrac23\cdot\tfrac{n^{2}}{2} = \tfrac{n^{2}}{3}$ and $\tfrac34\binom n2 = \tfrac{3n(n-1)}{8}$ : the inequality $\tfrac{n^{2}}{3} < \tfrac{3n(n-1)}{8}$ simplifies to $8n < 9(n-1)$ , i.e. $n > 9$ .

Check the boundary. For $n = 9$ : $t_3(9) = 27$ (parts $3,3,3$ ) and $\tfrac34\binom 92 = 27$ , so $T(9,3)$ meets the threshold and is $K_4$ -free — $n=9$ fails. For $n = 10$ : $t_3(10) = 33$ from the previous example while $\tfrac34\binom{10}{2} = 33.75$ , so any graph with at least $34$ edges exceeds $t_3(10)$ and contains a $K_4$ . The answer is $n = 10$ .□

Exercises for §7.4 →

7.5Corollaries: Independence, Supersaturation, Stability

Turán's theorem is a hub. Read in the complement it bounds independence numbers; read quantitatively it says a graph past the threshold contains not one forbidden clique but a positive proportion of all of them; read approximately it says near-extremal graphs must look like the extremal graph.

Corollary 7.25 (Mantel from Turán). Taking $r = 2$ in Turán's theorem recovers Mantel's theorem: $\mathrm{ex}(n,K_3) = t_2(n) = \lfloor n^{2}/4\rfloor$ , uniquely attained by $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$ .

Complementation turns "few edges forced by no clique" into "large independent set forced by few edges". Recall that $S \subseteq V(G)$ is independent if it spans no edge, and $\alpha(G)$ denotes the largest size of such a set; $S$ is independent in $G$ exactly when it is a clique in the complement $\overline G$ .

Theorem 7.26 (Caro–Wei). (Caro 1979, Wei 1981) Every graph $G$ satisfies

\alpha(G) \;\ge\; \sum_{v \in V(G)} \frac{1}{d(v) + 1}.

Proof. Take a uniformly random linear order $\prec$ on $V(G)$ and let

I = \{\, v : v \prec u \text{ for every } u \in N(v) \,\},

the set of vertices that come before all of their own neighbours.

$I$ is independent: if $u,v \in I$ were adjacent, then $u \prec v$ and $v \prec u$ , which is impossible.

For a fixed $v$ , the event $v \in I$ says that among the $d(v)+1$ vertices of $\{v\} \cup N(v)$ — whose relative order is uniformly random — $v$ comes first, which has probability $1/(d(v)+1)$ . By linearity of expectation $\mathbb{E}|I| = \sum_v 1/(d(v)+1)$ , and some outcome is at least the average, so $\alpha(G) \ge \mathbb E|I|$ .∎

Corollary 7.27 (Turán's bound on the independence number). A graph $G$ with $n$ vertices, $m$ edges and average degree $\bar d = 2m/n$ satisfies

\alpha(G) \;\ge\; \frac{n}{\bar d + 1} \;=\; \frac{n^{2}}{n + 2m}.

Equality holds exactly for disjoint unions of

\tfrac{n}{\bar d + 1}

equal cliques, i.e. for complements of Turán graphs.

Proof. The function $x \mapsto 1/(x+1)$ is convex on $x \ge 0$ , so by Jensen's inequality applied to the degree sequence,

\sum_{v} \frac{1}{d(v)+1} \;\ge\; \frac{n}{\bar d + 1},

and Caro–Wei finishes it. The right-hand side equals

n^{2}/(n+2m)

after substituting

\bar d = 2m/n

. In the complement this is Turán's theorem again:

\overline G

K_{r+1}

-free iff

\alpha(G) \le r

, and the extremal case of Jensen forces all degrees equal, which together with the Caro–Wei equality condition gives a disjoint union of equal cliques.∎

Example 7.28. A committee of $n = 30$ people has $60$ pairwise conflicts. How large a conflict-free subcommittee is guaranteed?

Solution. Model conflicts as edges: $n = 30$ , $m = 60$ , so $\bar d = 2\cdot 60/30 = 4$ .

By Turán's bound on the independence number, $\alpha(G) \ge n/(\bar d + 1) = 30/5 = 6$ : some six people are pairwise conflict-free.

The bound is sharp here — six disjoint copies of $K_5$ have $30$ vertices, $6\binom52 = 60$ edges and independence number exactly $6$ — and this graph is the complement of $T(30,6)$ , as the equality case predicts. Note that Caro–Wei would beat this whenever degrees are uneven: a graph with $59$ vertices of degree $2$ and one of huge degree has $\sum 1/(d(v)+1)$ much larger than $n/(\bar d+1)$ .□

Exceeding the Turán threshold does not merely produce one clique. It produces many, and the jump is immediate.

Theorem 7.29 (Supersaturation). (Erdős–Simonovits) For every $r \ge 2$ and every $\varepsilon > 0$ there is a $\delta > 0$ such that for all large $n$ : every graph on $n$ vertices with at least $t_r(n) + \varepsilon n^{2}$ edges contains at least $\delta n^{r+1}$ copies of $K_{r+1}$ .

Proof. Fix an integer $m > r$ , to be chosen at the end, and let $G$ have $n$ vertices and $e(G) \ge t_r(n) + \varepsilon n^{2}$ .

Pick an $m$ -subset $M \subseteq V(G)$ uniformly at random and let $X = e(G[M])$ . Each edge of $G$ survives in $\binom{n-2}{m-2}$ of the $\binom nm$ subsets, so

\mathbb{E}X = e(G)\cdot \frac{\binom{n-2}{m-2}}{\binom nm} = e(G)\cdot\frac{m(m-1)}{n(n-1)} \;\ge\; \bigl(t_r(n) + \varepsilon n^{2}\bigr)\frac{m(m-1)}{n^{2}}.

Now

t_r(n) \ge \left(1-\tfrac1r\right)\tfrac{n^{2}}{2} - \tfrac r8

and

t_r(m) \le \left(1-\tfrac1r\right)\tfrac{m^{2}}{2}

, so for

n

large,

\mathbb{E}X \;\ge\; \left(1 - \frac1r\right)\frac{m(m-1)}{2} + \varepsilon m(m-1) - o(1) \;\ge\; t_r(m) + \frac{\varepsilon}{2} m^{2} .

Write

p = \Pr\bigl[X > t_r(m)\bigr]

. Since

X \le \binom m2

always, and

X \le t_r(m)

otherwise,

\mathbb{E}X \;\le\; t_r(m) + p\binom m2 ,

p \ge \tfrac{\varepsilon}{2}m^{2} \big/ \binom m2 \ge \varepsilon

. By Turán's theorem every

m

-set with more than

t_r(m)

edges contains a

K_{r+1}

, so at least

\varepsilon\binom nm

of the

m

-sets do.

Each individual copy of $K_{r+1}$ in $G$ lies inside $\binom{n-r-1}{m-r-1}$ of the $m$ -sets, so the number of distinct copies is at least

\varepsilon\,\binom nm \Big/ \binom{n-r-1}{m-r-1} \;=\; \Theta_{\varepsilon, m}\!\left(n^{r+1}\right),

which is

\delta n^{r+1}

for a suitable

\delta = \delta(\varepsilon, m) > 0

. Any fixed

m > \max(r, 2/\varepsilon)

works.∎

Intuition. Supersaturation is the statement that the extremal threshold has no plateau. One might imagine graphs that sit just above $t_r(n)$ and contain a single stubborn clique; averaging rules that out, because "just above the threshold globally" means "above the threshold on a constant fraction of all small windows", and each such window contributes its own clique. The same averaging trick converts any extremal theorem into a counting theorem, which is why it is the standard first move in the field.

Finally, near-extremal graphs are near the extremal graph — not merely in edge count but in shape.

Theorem 7.30 (Erdős–Simonovits stability). For every $r \ge 2$ and $\varepsilon > 0$ there are $\delta > 0$ and $n_0$ such that: if $G$ is a $K_{r+1}$ -free graph on $n \ge n_0$ vertices with

e(G) \;\ge\; t_r(n) - \delta n^{2},

then

G

can be turned into

T(n,r)

by adding and deleting at most

\varepsilon n^{2}

edges. Equivalently,

G

differs from some complete

r

-partite graph in at most

\varepsilon n^{2}

edges.

Proof. (Sketch; the full argument uses the regularity method of the section Regularity, Removal and the Density Increment.) Suppose the conclusion fails for some $\varepsilon$ : then for every $\delta$ there is a $K_{r+1}$ -free graph, dense but $\varepsilon n^{2}$ -far from $r$ -partite. Apply the Szemerédi regularity lemma to such a graph and form the reduced graph on the clusters, joining two clusters when the pair is regular with density above a threshold. Being far from $r$ -partite forces the reduced graph to have an edge inside what would be a part, and the counting lemma then embeds a $K_{r+1}$ across the dense regular pairs, contradicting $K_{r+1}$ -freeness. The quantitative content — that the loss in edges from being $\varepsilon n^{2}$ -far is at least $\delta(\varepsilon) n^{2}$ — is exactly what the counting step supplies.∎

Remark. Stability is the engine behind many exact results. The standard strategy is: prove an asymptotic bound (often via Erdős–Stone), use stability to show an extremal graph is within $\varepsilon n^{2}$ of a known structure, and then run a local optimisation argument to force it to be exactly that structure. Erdős and Simonovits used it to determine $\mathrm{ex}(n,H)$ exactly for every $H$ with $\chi(H) \ge 3$ and large $n$ , in terms of a "decomposition family" that measures how $H$ sits inside blow-ups.

Exercises for §7.5 →

7.6Bipartite Forbidden Graphs and the Erdős–Stone Theorem

Turán's theorem answers the question for cliques. Two further theorems complete the picture: one determines the asymptotics for every non-bipartite $H$ , and the other opens the genuinely hard case, which is the bipartite one.

Theorem 7.31 (Erdős–Stone–Simonovits). (Erdős and Stone 1946; the form below is due to Erdős and Simonovits 1966) For every graph $H$ with at least one edge,

\mathrm{ex}(n, H) \;=\; \left(1 - \frac{1}{\chi(H) - 1}\right)\frac{n^{2}}{2} \;+\; o(n^{2}),

where

\chi(H)

is the chromatic number of

H

. Equivalently, the Turán density is

\pi(H) = 1 - \tfrac{1}{\chi(H)-1}

Proof. (Sketch, resting on the regularity lemma stated in the section Regularity, Removal and the Density Increment.) Lower bound: $T(n, \chi(H)-1)$ is $(\chi(H)-1)$ -colourable, so it cannot contain $H$ , which needs $\chi(H)$ colours; it has $t_{\chi(H)-1}(n) = \left(1 - \tfrac{1}{\chi(H)-1}\right)\tfrac{n^{2}}{2} + O(n)$ edges.

Upper bound: it suffices to show that for every $r$ and $t$ , a graph with $t_r(n) + \varepsilon n^{2}$ edges contains the complete $r+1$ -partite graph $K_{r+1}(t)$ with all parts of size $t$ , since $H$ embeds into $K_{\chi(H)}(|V(H)|)$ . By Supersaturation such a graph has $\delta n^{r+1}$ copies of $K_{r+1}$ ; a regularity partition plus the counting lemma upgrades "many copies of $K_{r+1}$ " to "a copy of the blown-up $K_{r+1}(t)$ ". This last step is the substance of the Erdős–Stone theorem and is what the regularity method was built to deliver.∎

The consequence is a clean dichotomy, and it is the single most quoted fact in the subject.

Corollary 7.32 (The chromatic dichotomy). If $\chi(H) = k \ge 3$ , then $\mathrm{ex}(n,H)$ is determined to leading order: it is $\left(1 - \tfrac{1}{k-1}\right)\tfrac{n^{2}}{2}(1+o(1))$ , the same as for $K_k$ . If $\chi(H) = 2$ — that is, $H$ is bipartite — the formula gives only $\mathrm{ex}(n,H) = o(n^{2})$ , and the leading-order behaviour is not determined.

Pitfall. The $o(n^{2})$ in Erdős–Stone is not a detail that "more care" removes. For $\chi(H) \ge 3$ the error term is genuinely smaller than the main term and the corollary is informative. For bipartite $H$ the main term is $0$ , so the theorem says only that $\mathrm{ex}(n,H)$ is subquadratic — true but nearly empty, since the truth is somewhere between $n^{1+c}$ and $n^{2-c}$ . This is the degenerate case, and determining the exponent even for $H = K_{4,4}$ is open.

For bipartite $H$ the first general bound is a counting argument on stars.

Theorem 7.33 (Kővári–Sós–Turán). (1954) Let $2 \le s \le t$ . Then

\mathrm{ex}(n, K_{s,t}) \;\le\; \frac{1}{2}(t-1)^{1/s}\,n^{2 - 1/s} + \frac{1}{2}(s-1)n .

In particular

\mathrm{ex}(n, K_{s,t}) = O(n^{2-1/s})

Proof. Let $G$ be $K_{s,t}$ -free on $n$ vertices with degrees $d_1,\dots,d_n$ and $e = e(G)$ edges. Count $s$ -stars: pairs $(S, v)$ where $|S| = s$ and $v$ is adjacent to every vertex of $S$ .

Counting by the centre $v$ , the number of such pairs is $\sum_{v} \binom{d_v}{s}$ .

Counting by $S$ : if some $s$ -set $S$ had $t$ or more common neighbours, those $t$ vertices together with $S$ would contain a $K_{s,t}$ . So each $S$ is counted at most $t-1$ times, and the total is at most $(t-1)\binom ns$ .

Hence $\sum_v \binom{d_v}{s} \le (t-1)\binom ns$ . The function $x \mapsto \binom xs$ (extended by $\binom xs = x(x-1)\cdots(x-s+1)/s!$ for $x \ge s-1$ , and $0$ below) is convex, so by Jensen

n\binom{\bar d}{s} \le \sum_v \binom{d_v}{s} \le (t-1)\binom ns \le (t-1)\frac{n^s}{s!},

with

\bar d = 2e/n

. Using

\binom{\bar d}{s} \ge (\bar d - s + 1)^s/s!

gives

(\bar d - s + 1)^s \le (t-1)n^{s-1}

, so

\bar d \;\le\; (t-1)^{1/s} n^{1 - 1/s} + s - 1 ,

and

e = n\bar d/2

gives the stated bound.∎

Corollary 7.34 (Reiman's bound for $C_4$ ). A graph on $n$ vertices with no $K_{2,2}$ — equivalently, in which no two vertices have two common neighbours, which for simple graphs means no $C_4$ — has at most $\tfrac14\bigl(1 + \sqrt{4n-3}\bigr)n$ edges, so $\mathrm{ex}(n,C_4) \le \tfrac12 n^{3/2}(1+o(1))$ .

Proof. Specialise the star count to $s = t = 2$ : $\sum_v \binom{d_v}{2} \le \binom n2$ . By convexity $n\binom{\bar d}{2} \le \binom n2$ , i.e. $\bar d^{2} - \bar d - (n-1) \le 0$ , whence $\bar d \le \tfrac12\bigl(1+\sqrt{4n-3}\bigr)$ and $e = n\bar d /2$ gives the bound.∎

Remark. Reiman's bound is asymptotically sharp. The Erdős–Rényi polarity graph takes the points of the projective plane $\mathrm{PG}(2,q)$ as vertices, joining $x$ and $y$ when $x_1y_1 + x_2y_2 + x_3y_3 = 0$ ; two distinct points lie on exactly one common line, so no two vertices have two common neighbours. It has $n = q^{2}+q+1$ vertices and $\tfrac12 q(q+1)^2$ edges, which is $\tfrac12 n^{3/2}(1+o(1))$ . Hence $\mathrm{ex}(n,C_4) = \tfrac12 n^{3/2}(1+o(1))$ along the sequence of prime powers, and the exponent $3/2$ is correct. Analogous algebraic constructions (norm graphs) settle the exponent for $K_{s,t}$ whenever $t > (s-1)!$ ; for $K_{4,4}$ and beyond nothing matching is known. A probabilistic deletion argument gives the general lower bound $\mathrm{ex}(n,K_{s,t}) = \Omega\bigl(n^{2 - (s+t-2)/(st-1)}\bigr)$ , which does not match Kővári–Sós–Turán.

Sparse bipartite graphs push the extremal number all the way down to linear.

Lemma 7.35 (Greedy tree embedding). If $\delta(G) \ge k-1$ then $G$ contains every tree $T$ on $k$ vertices.

Proof. Induct on $k$ . For $k = 1$ there is nothing to prove. Let $T$ have $k \ge 2$ vertices, let $x$ be a leaf of $T$ with neighbour $y$ , and let $T' = T - x$ , a tree on $k-1$ vertices. Since $\delta(G) \ge k - 1 \ge k-2$ , the induction hypothesis embeds $T'$ into $G$ by some map $\varphi$ . The image $\varphi(y)$ has at least $k-1$ neighbours in $G$ , while $\varphi(T')$ occupies only $k-2$ vertices other than $\varphi(y)$ ; so some neighbour $w$ of $\varphi(y)$ lies outside the image. Extending $\varphi$ by $x \mapsto w$ embeds $T$ .∎

Corollary 7.36 (Trees have linear extremal number). For every tree $T$ on $k$ vertices, $\mathrm{ex}(n, T) \le (k-2)n$ .

Proof. Let $G$ have $n$ vertices and $e(G) > (k-2)n$ edges. Repeatedly delete a vertex of degree at most $k-2$ , as long as one exists. Each deletion destroys at most $k-2$ edges and there are at most $n$ deletions, so fewer than $(k-2)n < e(G)$ edges are destroyed in total and the process stops at a non-empty subgraph $G'$ with $\delta(G') \ge k-1$ . By the Greedy tree embedding lemma $G'$ , and hence $G$ , contains $T$ . So a $T$ -free graph has at most $(k-2)n$ edges.∎

Remark. The truth is a factor of two better and is a genuine open problem in general. The Erdős–Sós conjecture asserts $\mathrm{ex}(n,T) \le \tfrac{k-2}{2}n$ for every tree $T$ on $k$ vertices — sharp because a disjoint union of copies of $K_{k-1}$ contains no tree on $k$ vertices and has exactly $\tfrac{k-2}{2}n$ edges when $(k-1)\mid n$ . It is proved for paths (the Erdős–Gallai theorem: a graph with more than $\tfrac{k-2}{2}n$ edges contains a path on $k$ vertices), for spiders and caterpillars, and, by an announced proof of Ajtai, Komlós, Simonovits and Szemerédi using the regularity method, for all trees with $k$ large.

Example 7.37. Bound the number of edges of a $C_4$ -free graph on $n = 21$ vertices, and compare with the polarity construction.

Solution. By Reiman's bound, $e \le \tfrac14\bigl(1+\sqrt{4\cdot 21 - 3}\bigr)\cdot 21 = \tfrac{21}{4}\bigl(1 + \sqrt{81}\bigr) = \tfrac{21}{4}\cdot 10 = 52.5$ , so $e \le 52$ .

The polarity graph of $\mathrm{PG}(2,4)$ has $q = 4$ , hence $n = 4^2+4+1 = 21$ vertices and $\tfrac12\cdot 4\cdot 25 = 50$ edges — within two of the bound. So the true value of $\mathrm{ex}(21,C_4)$ lies between $50$ and $52$ : Reiman's bound is tight to within a lower-order term rather than exactly.

By contrast $\mathrm{ex}(21, K_3) = \lfloor 441/4\rfloor = 110$ , more than twice as large: forbidding a bipartite graph is a far more severe restriction than forbidding a triangle, exactly as The chromatic dichotomy predicts.□

Exercises for §7.6 →

7.7Density in the Integers: Roth and Szemerédi

Every theorem so far has the same logical shape: enough density forces a fixed pattern. Turán forces a clique once the edge density passes $1 - 1/r$ ; Erdős–Stone forces any $H$ once it passes $1 - 1/(\chi(H)-1)$ . The most celebrated instance of that shape lives not in graphs but in the integers, and — as the next section shows — it is proved with the tools of extremal graph theory.

Definition 7.38 (Upper density and the counting function $r_k$ ). For $A \subseteq \mathbb{N}$ the upper density of $A$ is

\overline d(A) = \limsup_{N \to \infty} \frac{|A \cap \{1,\dots,N\}|}{N}.

For integers

k \ge 3

and

N \ge 1

, let

r_k(N)

denote the largest size of a subset of

\{1,\dots,N\}

containing no

k

-term arithmetic progression

a, a+d, \dots, a+(k-1)d

with

d \ge 1

. A progression with

d = 0

is trivial and does not count.

$r_k(N)$ is the extremal function of this world, exactly parallel to $\mathrm{ex}(n,H)$ : the largest an object can be while avoiding a pattern. The prehistory is a colouring theorem rather than a density theorem.

Theorem 7.39 (van der Waerden). (1927) For all integers $k, c \ge 1$ there is an $N = W(k,c)$ such that every colouring of $\{1,\dots,N\}$ with $c$ colours contains a monochromatic $k$ -term arithmetic progression.

Proof. (Sketch; the standard proof is a double induction on $k$ and on the number of colours, using "colour focusing".) One shows by induction on $k$ the stronger statement that long blocks of consecutive integers, coloured arbitrarily, must repeat their colour patterns, so that a family of $k-1$ progressions of length $k-1$ can be constructed all "focused" on a single further point; whichever colour that focus receives completes one of them to a monochromatic progression of length $k$ . The induction gives no reasonable bound — the resulting $W(k,c)$ is of Ackermann type, and Shelah's later proof brought it down to primitive recursive.∎

Erdős and Turán observed in 1936 that a density statement would imply van der Waerden's colouring statement at once: in any $c$ -colouring of $\{1,\dots,N\}$ some colour class has at least $N/c$ elements, so a theorem of the form "a set of size $\ge \delta N$ contains a $k$ -AP" covers it. They conjectured exactly that. The case $k = 3$ took seventeen years.

Theorem 7.40 (Roth). (1953) $r_3(N) = o(N)$ . Quantitatively, Roth proved $r_3(N) = O\!\left(N/\log\log N\right)$ .

Theorem 7.41 (Szemerédi). (1975) For every $k \ge 3$ , $r_k(N) = o(N)$ . Equivalently: every set $A \subseteq \mathbb{N}$ with $\overline d(A) > 0$ contains arithmetic progressions of every finite length — indeed infinitely many of each length.

The two formulations really are equivalent, and the translation is worth doing once because it explains why a statement about the infinite set $\mathbb N$ can be attacked by finite combinatorics.

Proposition 7.42 (Finite and infinite forms agree). Fix $k \ge 3$ . Then $r_k(N) = o(N)$ if and only if every $A \subseteq \mathbb N$ with $\overline d(A) > 0$ contains a $k$ -term arithmetic progression.

Proof. ( $\Rightarrow$ ) Let $\overline d(A) = \delta > 0$ . Then $|A \cap \{1,\dots,N\}| \ge \tfrac{\delta}{2}N$ for infinitely many $N$ . Since $r_k(N)/N \to 0$ , for all large $N$ we have $r_k(N) < \tfrac\delta2 N$ , so for any such large $N$ the set $A \cap \{1,\dots,N\}$ is too big to be $k$ -AP-free and contains a $k$ -AP. Taking larger and larger $N$ and noting that a $k$ -AP found in $\{1,\dots,N\}$ can be avoided only finitely often, $A$ contains infinitely many.

( $\Leftarrow$ ) Suppose $r_k(N) \ge \delta N$ for some $\delta>0$ and infinitely many $N$ ; we build a set of positive upper density with no $k$ -AP. Choose $N_1 < N_2 < \cdots$ growing fast enough that $N_{i} > i\,(N_1 + \cdots + N_{i-1})$ , and for each $i$ a $k$ -AP-free set $A_i \subseteq \{1,\dots,N_i\}$ with $|A_i| \ge \delta N_i$ . Place a translated copy of $A_i$ inside a block of length $N_i$ starting far beyond everything used so far and separated by long gaps, with the blocks' spacings chosen generically so that no progression can straddle two blocks. The union $A$ has $\overline d(A) \ge \delta / 2$ along the block ends, yet every $k$ -AP would have to lie inside one block, where none exists.∎

Pitfall. Positive upper density is sufficient, never necessary. The primes have density zero and yet contain arbitrarily long progressions (Green–Tao); the squares have density zero and contain no four-term progression at all. A density-zero hypothesis simply puts the set outside the theorem's reach — it says nothing either way. Equally, note that $\overline d$ is a $\limsup$ : the ordinary density need not exist for Szemerédi to apply.

How far from $o(N)$ can a $k$ -AP-free set be? The lower bound is a construction of Behrend, and it is the reason the quantitative problem is hard.

Theorem 7.43 (Behrend's construction). (1946) There is a constant $c > 0$ such that for all large $N$ ,

r_3(N) \;\ge\; N \exp\!\bigl(-c\sqrt{\log N}\,\bigr).

In particular

r_3(N)

is larger than

N^{1-\varepsilon}

for every

\varepsilon>0

: no power saving is possible.

Proof. (Sketch of the construction; the verification is elementary.) Fix integers $d$ and $m$ and consider the cube $C = \{0,1,\dots,d-1\}^m$ . Split $C$ by the value of $\|x\|^2 = x_1^2 + \cdots + x_m^{2}$ , which ranges over at most $m d^{2}$ values, so some sphere $S_R = \{x \in C : \|x\|^2 = R\}$ contains at least $d^m/(md^{2})$ points.

A sphere in Euclidean space is strictly convex, so it contains no three points $u,v,w$ with $u + w = 2v$ unless $u = v = w$ : the midpoint of a chord lies strictly inside. Hence $S_R$ is free of three-term progressions as a subset of $\mathbb{Z}^m$ .

Now map $x \mapsto \sum_{i} x_i (2d)^{i-1}$ , a base- $2d$ encoding. Because every digit is less than $d$ , adding two elements of $C$ produces no carries, so the map sends progressions to progressions and is injective. The image is a $3$ -AP-free subset of $\{1,\dots,N\}$ with $N = (2d)^m$ and size at least $d^m/(md^{2})$ . Optimising $m \approx \sqrt{\log N}$ against $d$ gives the stated bound.∎

Intuition. Behrend's set is thin only in the way a sphere is thin inside a cube. Convexity is exactly the geometric form of "no three points in arithmetic progression", and lifting it to high dimension, where a cube has exponentially many points but only polynomially many possible radii, is what makes the loss sub-polynomial. Any proof of Roth's theorem must lose at least this much, which is why bounds of the shape $N/\log\log N$ or $N \exp(-(\log N)^{c})$ are the natural currency rather than $N^{1-c}$ .

Example 7.44. Decide what Szemerédi's theorem says about (a) the even numbers, (b) the perfect squares, (c) a set containing every integer in $[10^{2k}, 2\cdot 10^{2k}]$ for every $k$ and nothing else.

Solution. (a) $|2\mathbb N \cap \{1,\dots,N\}| = \lfloor N/2\rfloor$ , so $\overline d = \tfrac12 > 0$ and the theorem applies: the evens contain $k$ -APs for every $k$ — visibly so, since $2, 4, \dots, 2k$ is one.

(b) $|\{n^{2}\} \cap \{1,\dots,N\}| = \lfloor\sqrt N\rfloor$ , so $\overline d = \lim \sqrt N/N = 0$ and the theorem is silent. In fact a classical result of Fermat says no four distinct squares are in arithmetic progression, so the squares contain no $4$ -AP — a density-zero set may genuinely lack long progressions.

(c) Along $N = 2 \cdot 10^{2k}$ the set occupies about half of $\{1,\dots,N\}$ , so $\overline d \ge \tfrac12 > 0$ even though the ordinary density does not exist (along $N = 10^{2k+1}$ the ratio is nearly $0$ ). Szemerédi applies, because the definition uses $\limsup$ , and indeed each block $[10^{2k},2\cdot10^{2k}]$ is a long interval and contains progressions of every length.□

Remark. Erdős conjectured a far stronger statement: if $\sum_{a \in A} 1/a = \infty$ then $A$ contains $k$ -term progressions for every $k$ . This would imply Green–Tao for the primes, since $\sum_p 1/p$ diverges. It remains open for $k \ge 4$ ; Bloom and Sisask proved the case $k = 3$ in 2020.

Exercises for §7.7 →

7.8Regularity, Removal and the Density Increment

Szemerédi's original proof of his theorem introduced a tool that has outgrown it: the regularity lemma, which says that every graph, however large and however irregular, is approximately a bounded-size weighted graph. It is the reason this theorem belongs in a chapter on extremal graph theory, and — through the removal lemma — it gives a complete proof of Roth's theorem in the language of triangles.

Definition 7.45 (Density and $\varepsilon$ -regular pairs). For disjoint vertex sets $X, Y$ in a graph $G$ , the density of the pair is $d(X,Y) = e(X,Y)/(|X||Y|)$ , where $e(X,Y)$ counts edges with one end in each. The pair $(X,Y)$ is $\varepsilon$ -regular if for all $X' \subseteq X$ , $Y' \subseteq Y$ with $|X'| \ge \varepsilon|X|$ and $|Y'| \ge \varepsilon|Y|$ ,

\bigl| d(X',Y') - d(X,Y) \bigr| \;\le\; \varepsilon .

A partition

V(G) = V_1 \cup \cdots \cup V_k

is equitable if the part sizes differ by at most

1

, and $\varepsilon$ -regular if all but at most

\varepsilon k^{2}

of the pairs

(V_i,V_j)

are

\varepsilon

-regular.

Theorem 7.46 (Szemerédi regularity lemma). (1975) For every $\varepsilon > 0$ and every $m \ge 1$ there is an $M = M(\varepsilon,m)$ such that every graph with at least $m$ vertices admits an $\varepsilon$ -regular equitable partition into $k$ parts with $m \le k \le M$ .

Proof. (Sketch; the argument is a potential-function increment.) Define the mean square density (or index) of a partition $P$ into parts $V_i$ as

q(P) = \sum_{i<j} \frac{|V_i||V_j|}{n^{2}}\, d(V_i,V_j)^2 \in [0,1] .

Refining a partition never decreases

q

(by convexity of

x \mapsto x^{2}

), and — this is the heart — if a partition is not

\varepsilon

-regular, then the witnesses

X', Y'

of irregularity can be used to refine it in a way that increases

q

by at least

\varepsilon^{5}/2

. Since

q \le 1

, at most

2\varepsilon^{-5}

refinements can occur, so the process terminates at a regular partition. Each refinement can multiply the number of parts by

2^k

, which is why the bound

M(\varepsilon,m)

is a tower of twos of height

\varepsilon^{-5}

or so; Gowers proved a tower-type bound is genuinely necessary.∎

Lemma 7.47 (Triangle counting lemma). Let $V_1,V_2,V_3$ be disjoint sets of size $t$ such that each pair $(V_i,V_j)$ is $\varepsilon$ -regular with density $d_{ij} \ge 2\varepsilon$ . Then the number of triangles with one vertex in each $V_i$ is at least

(1 - 2\varepsilon)\,(d_{12}-\varepsilon)(d_{13}-\varepsilon)(d_{23}-\varepsilon)\, t^{3} .

Proof. (Sketch.) Call $v \in V_1$ typical if it has at least $(d_{12}-\varepsilon)t$ neighbours in $V_2$ and at least $(d_{13}-\varepsilon)t$ neighbours in $V_3$ . Regularity forbids more than $\varepsilon t$ vertices from failing either condition — the set of failures would otherwise be a large subset witnessing a density drop — so at least $(1-2\varepsilon)t$ vertices are typical. For a typical $v$ , its neighbourhoods $N_2 \subseteq V_2$ and $N_3 \subseteq V_3$ each have size at least $\varepsilon t$ , so $\varepsilon$ -regularity of $(V_2,V_3)$ applies to them and gives $e(N_2,N_3) \ge (d_{23}-\varepsilon)|N_2||N_3|$ edges, each completing a triangle through $v$ . Multiplying gives the bound.∎

Theorem 7.48 (Triangle removal lemma). (Ruzsa and Szemerédi, 1976) For every $\varepsilon > 0$ there is a $\delta > 0$ such that: if a graph $G$ on $n$ vertices contains fewer than $\delta n^{3}$ triangles, then there is a set of at most $\varepsilon n^{2}$ edges whose deletion makes $G$ triangle-free.

Proof. Apply the Szemerédi regularity lemma with parameter $\varepsilon/4$ and $m = 4/\varepsilon$ to get an equitable $(\varepsilon/4)$ -regular partition into $k \le M$ parts, each of size $t \approx n/k$ . Now delete three kinds of edges:

edges inside a part: at most $k \cdot \binom{t}{2} \le n^{2}/(2k) \le \varepsilon n^{2} / 8$ of them, since $k \ge 4/\varepsilon$ ;
edges in pairs that are not $(\varepsilon/4)$ -regular: at most $(\varepsilon/4)k^{2} \cdot t^{2} \le \varepsilon n^{2}/4$ ;
edges in regular pairs of density less than $\varepsilon/2$ : at most $\binom k2 \cdot (\varepsilon/2) t^{2} \le \varepsilon n^{2}/4$ .

In total at most $\varepsilon n^{2}$ edges are deleted. Suppose the resulting graph $G'$ still has a triangle, with vertices in parts $V_{i}, V_j, V_l$ — necessarily distinct by (1), pairwise regular by (2) and of density at least $\varepsilon/2$ by (3). Then the Triangle counting lemma applies with $\varepsilon/4$ in place of $\varepsilon$ and densities at least $\varepsilon/2$ , producing at least

\tfrac12\left(\tfrac{\varepsilon}{4}\right)^3 t^{3} \;\ge\; \tfrac12\left(\tfrac{\varepsilon}{4}\right)^3 \left(\frac{n}{2M}\right)^{3} =: \delta n^{3}

triangles in $G$ — the counting lemma counts triangles of the original graph, since deleting edges only removed some. Choosing

\delta

as displayed, this contradicts the hypothesis that

G

has fewer than

\delta n^{3}

triangles. Hence

G'

is triangle-free.∎

Intuition. The removal lemma says triangles come in crowds or not at all. A graph cannot contain a few scattered triangles that are nevertheless impossible to destroy cheaply: either you can wipe them out with a vanishing fraction of the edges, or there were already a constant fraction of all possible triangles. This "few implies removable" shape recurs everywhere in the subject — it is the exact statement that makes triangle-freeness testable by sampling a constant number of vertices, and the ancestor of property testing.

The payoff is Roth's theorem, obtained by turning an arithmetic problem into a triangle problem.

Theorem 7.49 (Roth's theorem via triangle removal). If $A \subseteq \{1,\dots,N\}$ contains no three-term arithmetic progression with positive common difference, then $|A| = o(N)$ .

Proof. Let $M = 3N + 1$ and work in $\mathbb{Z}_M$ . Build a tripartite graph $G$ on $V = X \cup Y \cup Z$ , where each of $X, Y, Z$ is a copy of $\mathbb{Z}_M$ , so $|V| = n = 3M$ , with edges

x \sim y \iff y - x \in A, \qquad y \sim z \iff z - y \in A, \qquad x \sim z \iff z - x \in 2\!\cdot\!A ,

where

2\!\cdot\!A = \{2a : a \in A\}

Triangles correspond to progressions. A triangle $xyz$ means $y - x = a_1$ , $z - y = a_2$ and $z - x = 2a_3$ with $a_1,a_2,a_3 \in A$ ; adding the first two gives $a_1 + a_2 = 2a_3$ in $\mathbb{Z}_M$ , and since both sides lie in $\{2,\dots,2N\}$ with $M > 3N$ there is no wrap-around, so the equation holds in $\mathbb Z$ . Thus $a_1, a_3, a_2$ is a three-term progression in $A$ , which by hypothesis must be trivial: $a_1 = a_2 = a_3$ .

Counting. Conversely, for each $x \in \mathbb{Z}_M$ and each $a \in A$ the triple $(x,\, x+a,\, x+2a)$ is a triangle. So $G$ has exactly $M|A|$ triangles, and these are pairwise edge-disjoint: an edge $xy$ determines $a = y-x$ and hence the whole triangle. Destroying all triangles therefore requires deleting at least $M|A|$ edges.

Applying removal. The triangle count is $M|A| \le MN \le n^{2} = o(n^{3})$ , so for any $\varepsilon > 0$ , once $n$ is large the hypothesis of the Triangle removal lemma holds with the relevant $\delta$ ; hence $\varepsilon n^{2}$ edge deletions suffice to destroy all triangles. Combining the two counts,

M|A| \;\le\; \varepsilon n^{2} = 9\varepsilon M^{2} \quad\Longrightarrow\quad |A| \le 9\varepsilon M \le 30\,\varepsilon N .

\varepsilon > 0

was arbitrary,

|A|/N \to 0

.∎

Figure 7.50. The Ruzsa–Szemerédi encoding behind Roth's theorem. Each triangle of the tripartite graph reads off three elements

a_1 = y-x

a_2 = z-y

and

a_3 = (z-x)/2

A

satisfying

a_1 + a_2 = 2a_3

— that is, a three-term progression

a_1, a_3, a_2

. If

A

has no non-trivial progression the only triangles are the

M|A|

with

a_1 = a_2 = a_3

, and those are pairwise edge-disjoint, so removing them all is expensive — which the removal lemma forbids unless

A

is small.

Roth's own proof (1953) predates all of this and runs on Fourier analysis. It is worth recording because its density increment strategy is the template for the whole quantitative theory.

Proof. (Sketch of Roth's Fourier proof.) Let $A \subseteq \{1,\dots,N\}$ have density $\delta = |A|/N$ and no non-trivial $3$ -AP. Write $\widehat{1_A}(\theta) = \sum_{a\in A} e^{2\pi i a \theta}$ .

Dichotomy. Either every non-trivial Fourier coefficient is small, $|\widehat{1_A}(\theta)| \le \tfrac{\delta^{2}}{10} N$ for all $\theta \ne 0$ , or some coefficient is large.

Uniform case. Expanding the count of three-term progressions in $A$ as a Fourier integral, the zero frequency contributes $\delta^{3} N^{2}$ and all other frequencies contribute at most $\max_{\theta\ne0}|\widehat{1_A}(\theta)| \cdot \sum_\theta |\widehat{1_A}(\theta)|^2 / N \le \tfrac{\delta^{2}}{10}N \cdot \delta N$ . So there are at least $\tfrac12 \delta^{3} N^{2}$ progressions, far more than the $N$ trivial ones once $N > 2\delta^{-3}$ — a contradiction.

Structured case. If $|\widehat{1_A}(\theta)| > \tfrac{\delta^{2}}{10}N$ for some $\theta \ne 0$ , then $A$ correlates with the level sets of $x \mapsto \theta x$ , which partition $\{1,\dots,N\}$ into arithmetic progressions of length about $\sqrt N$ on which $e^{2\pi i \theta x}$ is nearly constant. On one of them $A$ has density at least $\delta + c\delta^{2}$ .

Iteration. Rescale that progression to look like $\{1,\dots,N'\}$ with $N' \approx \sqrt N$ and repeat. Density increases by $c\delta^{2}$ each time, so after $O(1/\delta)$ steps it would exceed $1$ ; the iteration must therefore terminate in the uniform case, which forces $\delta = O(1/\log\log N)$ .∎

Remark. Szemerédi's theorem for general $k$ resisted Fourier analysis for decades: a set can be perfectly uniform in the Fourier sense and still have the wrong number of $4$ -APs — the standard example is $\{x : x^{2}\alpha \bmod 1 \in I\}$ , whose obstruction is quadratic, not linear. Repairing this is what Gowers's uniformity norms $\|f\|_{U^s}$ do, and the corresponding inverse theorem — large $U^s$ norm implies correlation with a nilsequence — is due to Green, Tao and Ziegler. A third, entirely different proof was given by Furstenberg in 1977: his correspondence principle converts a set of positive upper density into a measure-preserving system $(X,\mathcal B,\mu,T)$ and a set $E$ with $\mu(E) = \overline d(A)$ , so that Szemerédi's theorem becomes the multiple recurrence statement

\liminf_{M\to\infty}\frac1M\sum_{d=1}^{M}\mu\bigl(E \cap T^{-d}E \cap \cdots \cap T^{-(k-1)d}E\bigr) > 0 .

The ergodic proof is qualitative — it gives no bound at all on

r_k(N)

— but it generalises in directions the finitary proofs did not initially reach.

Example 7.51. Explain why the triangle removal lemma cannot be improved to a bound of the form $\delta = \mathrm{poly}(\varepsilon)$ .

Solution. Suppose the lemma held with $\delta(\varepsilon) \ge c\,\varepsilon^{C}$ for absolute constants $c > 0$ and $C > 1$ . Run Roth's theorem via triangle removal backwards on a Behrend set.

Take $A \subseteq \{1,\dots,N\}$ with no non-trivial $3$ -AP and $|A| = \rho N$ , and build the tripartite graph $G$ on $n = 3M$ vertices with $M = 3N+1$ , so $M \le 4N$ and $n \le 12N$ . As established in that proof, $G$ has exactly $M|A|$ triangles and they are pairwise edge-disjoint, so making $G$ triangle-free costs at least $M|A|$ edge deletions, i.e. $\varepsilon_0 n^{2}$ deletions with

\varepsilon_0 = \frac{M|A|}{n^{2}} = \frac{|A|}{9M} \;\ge\; \frac{\rho}{36},

while the triangle density is

\alpha = M|A|/n^{3} = |A|/(27M^{2}) \le \rho/(27 \cdot 9 N)

, so

\alpha \le \rho/(243 N)

Apply the lemma with $\varepsilon = \varepsilon_0/2$ : since $\varepsilon_0 n^{2}/2$ deletions provably do not suffice, the hypothesis must fail, i.e. $\alpha \ge \delta(\varepsilon_0/2) \ge c(\varepsilon_0/2)^{C}$ . Substituting both estimates,

\frac{\rho}{243\,N} \;\ge\; c\left(\frac{\rho}{72}\right)^{C} \quad\Longrightarrow\quad \rho^{\,1-C} \;\ge\; c''\,N \quad\Longrightarrow\quad \rho \;\le\; (c''N)^{-1/(C-1)} .

That is a power saving:

r_3(N) = O\bigl(N^{1 - 1/(C-1)}\bigr)

But Behrend's construction supplies $3$ -AP-free sets of size $Ne^{-c'\sqrt{\log N}}$ , which exceeds $N^{1-\eta}$ for every fixed $\eta > 0$ once $N$ is large. The two are incompatible, so no polynomial $\delta(\varepsilon)$ exists. The best known $\delta$ is tower-type, inherited from the regularity lemma, and improving it is equivalent to improving the bound in Roth's theorem.□

Exercises for §7.8 →

7.9Green–Tao and the Reach of the Method

The regularity–removal machinery spread far beyond its origin. This section records where the two strands of the chapter — extremal graph theory and density theorems for the integers — ended up, and how they feed back into each other.

Theorem 7.52 (Green–Tao). (2004) The primes contain arbitrarily long arithmetic progressions: for every $k$ there are primes $p_1 < p_2 < \cdots < p_k$ in arithmetic progression.

Proof. (Sketch, resting on Szemerédi.) The primes have density zero in $\{1,\dots,N\}$ — about $1/\log N$ — so Szemerédi's theorem does not apply directly. Green and Tao prove a relative Szemerédi theorem: if $\nu$ is a pseudorandom measure on $\{1,\dots,N\}$ — a non-negative weight satisfying certain linear-forms and correlation conditions that make it behave like the constant function $1$ for the purposes of counting progressions — then any subset of positive relative density with respect to $\nu$ contains $k$ -APs. They then construct such a $\nu$ supported essentially on almost-primes, using sieve weights of Goldston and Yıldırım, with respect to which the primes have positive relative density. The transference step deduces the relative theorem from the absolute one by approximating the relatively dense set by a genuinely dense one.∎

Remark. The theorem is ineffective in the sense that matters for examples: it guarantees $k$ -term progressions of primes for every $k$ , but the smallest known explicit ones grow enormous — the record progressions have around $27$ terms and involve numbers of dozens of digits. Note also what it does not say: it makes no claim about progressions of consecutive primes, a much harder statement (known for $k \le 3$ unconditionally and in general only under strong hypotheses).

Example 7.53. Exhibit a $5$ -term arithmetic progression of primes, and explain why the common difference must be divisible by $6$ for any $k \ge 5$ progression of primes above $5$ .

Solution. $5, 11, 17, 23, 29$ works: the differences are $11-5 = 17-11 = 23-17 = 29-23 = 6$ , and all five terms are prime.

For the divisibility claim, let $p_1, \dots, p_k$ be primes greater than $k$ in arithmetic progression with common difference $d$ , and let $q \le k$ be a prime. The residues $p_1, p_1 + d, \dots, p_1 + (k-1)d$ modulo $q$ run through all residues if $q \nmid d$ , since $d$ is then invertible mod $q$ and $k \ge q$ ; in particular one term would be divisible by $q$ and hence equal to $q$ , contradicting $p_i > k \ge q$ . So $q \mid d$ for every prime $q \le k$ . For $k = 5$ this gives $2 \mid d$ and $3 \mid d$ , hence $6 \mid d$ — and indeed $5 \mid d$ as well unless the progression starts at $5$ , which is exactly the loophole our example uses.□

The proof technique generalised in several independent directions.

Theorem 7.54 (Multidimensional Szemerédi). (Furstenberg and Katznelson, 1978) Let $F \subseteq \mathbb{Z}^m$ be finite and let $S \subseteq \mathbb{Z}^m$ have positive upper Banach density. Then $S$ contains a homothetic copy $a + dF$ of $F$ for some $a \in \mathbb{Z}^m$ and $d \ge 1$ .

Theorem 7.55 (Polynomial Szemerédi). (Bergelson and Leibman, 1996) Let $p_1,\dots,p_k \in \mathbb{Z}[x]$ satisfy $p_i(0) = 0$ . If $\overline d(A) > 0$ then there are $a$ and $d \ge 1$ with $a + p_1(d), \dots, a + p_k(d)$ all in $A$ . Taking $p_i(x) = (i-1)x$ recovers Szemerédi's theorem; taking $k=1$ , $p_1(x) = x^{2}$ gives a square difference inside every dense set.

Remark. Both were originally proved by ergodic methods only; combinatorial proofs came later, through the hypergraph regularity and removal lemmas of Gowers and of Rödl, Nagle, Schacht and Skokan, which also yield a fourth proof of Szemerédi's theorem for all $k$ by exactly the argument used above for $k=3$ — $k$ -APs become "simplices" in a $(k-1)$ -uniform hypergraph, and the hypergraph removal lemma finishes it.

Quantitatively the subject is still open in every direction that matters.

Theorem 7.56 (Quantitative bounds for $r_3$ and $r_k$ ). Gowers (2001) proved $r_k(N) \le N(\log\log N)^{-c_k}$ for every $k$ , the first effective bound for $k \ge 4$ . For $k=3$ , Kelley and Meka (2023) proved

r_3(N) \;\le\; N\exp\!\left(-c(\log N)^{\beta}\right)

for absolute constants

c, \beta > 0

, which is of the same shape as Behrend's construction and leaves only the value of the exponent in doubt.

Meanwhile the graph-theoretic side of the chapter absorbed the same tools.

Theorem 7.57 (Graph removal lemma). (Erdős, Frankl and Rödl, 1986) For every graph $H$ and every $\varepsilon > 0$ there is $\delta > 0$ such that any $n$ -vertex graph with fewer than $\delta n^{|V(H)|}$ copies of $H$ can be made $H$ -free by deleting at most $\varepsilon n^{2}$ edges.

Corollary 7.58 (Ruzsa–Szemerédi $(6,3)$ -theorem). If a $3$ -uniform hypergraph on $n$ vertices has the property that no $6$ vertices span $3$ or more edges, then it has $o(n^{2})$ edges. Equivalently, a graph on $n$ vertices whose edge set is the disjoint union of $n$ induced matchings has $o(n^{2})$ edges.

Proof. (Sketch.) Encode the hypergraph as a tripartite graph exactly as in Roth's theorem via triangle removal: each hyperedge becomes a triangle, and the $(6,3)$ -condition forces the triangles to be edge-disjoint and to be the only ones. Edge-disjointness makes destroying them expensive; the removal lemma says it must be cheap unless there are few, so there are $o(n^{2})$ of them.∎

Remark. Three further descendants are worth naming. Property testing: the removal lemma is precisely the statement that $H$ -freeness is testable — a randomised algorithm sampling a constant number of vertices distinguishes $H$ -free graphs from those $\varepsilon$ -far from $H$ -free. Graph limits: the space of graphons, with the cut metric, makes the regularity lemma a compactness statement, and Turán-type problems become optimisation over a compact space. Flag algebras: Razborov's formalism turns the Lagrangian viewpoint of Motzkin–Straus into a semidefinite program, and has settled numerous extremal densities — including the asymptotic version of the triangle supersaturation problem solved by Razborov, Nikiforov and Reiher — that resisted hand arguments.

Intuition. The unifying moral of the chapter is that density leaves no room to hide. Push the edge density past $1-1/r$ and a clique appears; push it past that by a constant and a positive proportion of all cliques appear; push a set of integers past density zero and every progression appears. In each case the proof finds a scale at which the object looks random, and a random object of that density simply contains the pattern. Extremal theorems are the statement that structure and randomness are the only two options.

Exercises for §7.9 →

Common Mistakes

**Confusing "contains $H$ " with "contains $H$ as an induced subgraph"**: $\mathrm{ex}(n,H)$ uses ordinary containment. Every graph with a $K_4$ contains $C_4$ , so $C_4$ -free is a much stronger condition than "no induced $4$ -cycle".
Assuming the extremal graph is always a Turán graph: only when $H$ is a clique. For bipartite $H$ the extremal graphs are algebraic or random-like — incidence graphs of projective planes, norm graphs — and look nothing like a balanced blow-up.
Forgetting the uniqueness clause, or over-reading it: $T(n,r)$ is the *unique* maximiser, so complete $r$ -partite graphs with unbalanced parts are strictly worse; but uniqueness is a statement about the exact maximum, not about graphs slightly below it — those are governed by *Erdős–Simonovits stability*.
**Treating the $o(n^{2})$ in Erdős–Stone as harmless**: for bipartite $H$ the main term is zero and the theorem gives no information beyond subquadratic. The whole degenerate case, including $\mathrm{ex}(n,K_{4,4})$ , lives inside that error term.
**Expecting quadratic extremal numbers for sparse $H$ **: for a tree on $k$ vertices $\mathrm{ex}(n,T)$ is *linear* in $n$ ; the Erdős–Sós conjecture puts it at $\tfrac{k-2}{2}n$ , and the easy argument via minimum degree gives $(k-2)n$ .
Misreading Kővári–Sós–Turán as an equality: it is an upper bound $O(n^{2-1/s})$ , matched by constructions only for $s = 2, 3$ and for $t$ large relative to $s$ .
Confusing extremal and Ramsey statements: Turán's theorem maximises edges in an uncoloured graph before a clique is forced; Ramsey's theorem forces a monochromatic clique in *any* colouring of a large complete graph, regardless of density. Neither implies the other.
Applying Szemerédi's theorem to a density-zero set: positive upper density is a hypothesis, not a conclusion. The squares have density zero and no $4$ -AP; the primes have density zero and do have $k$ -APs (*Green–Tao*). The theorem simply does not speak about either.
Confusing upper density with natural density: $\overline d$ is a $\limsup$ , so a set whose density oscillates still qualifies. Demanding the limit exists is a strictly stronger hypothesis than the theorem needs.
Attributing the ergodic proof to Szemerédi: Szemerédi's 1975 proof is combinatorial and introduced the regularity lemma; Furstenberg's 1977 proof is the ergodic one, and it gives no quantitative bound.
Believing the quantitative bounds are usable: every proof of Szemerédi's theorem for $k \ge 4$ yields bounds that are astronomically weak, and the regularity lemma's tower-type dependence is known to be necessary. For concrete computations one falls back on van der Waerden numbers, which are themselves only known for the tiniest cases.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Graph Coloring and Ramsey Theory The Probabilistic Method →

Helpful?