mit18_225_f23_lec02-05

MIT OCW: Graph Theory and Additive Combinatorics --- Yufei Zhao
Forbidding a Subgraph
Chapter Highlights
• Turán problem: determine the maximum number of edges in an 𝑛-vertex 𝐻-free graph
• Mantel’s and Turán’s theorems: 𝐾𝑟 -free
• Kővári–Sós–Turán theorem: 𝐾 𝑠,𝑡 -free
• Erdős–Stone–Simonovits theorem: 𝐻-free for general 𝐻
• Dependent random choice technique: 𝐻-free for a bounded degree bipartite 𝐻
• Lower bound constructions of 𝐻-free graphs for bipartite 𝐻
• Algebraic constructions: matching lower bounds for 𝐾2,2 , 𝐾3,3 , and 𝐾 𝑠,𝑡 for 𝑡 much larger
than 𝑠, and also for 𝐶4 , 𝐶6 , 𝐶10
• Randomized algebraic constructions
We begin by completely answering the following question.
Question 1.0.1 (Triangle-free graph)

What is the maximum number of edges in a triangle-free 𝑛-vertex graph?
We will see the answer shortly. More generally, we can ask about what happens if we
replace “triangle” by an arbitrary subgraph. This is a foundational problem in extremal graph
theory.
Definition 1.0.2 (Extremal number / Turán number)

We write ex(𝒏, 𝑯) for the maximum number of edges in an 𝑛-vertex 𝐻-free graph. Here
an 𝑯-free graph is a graph that does not contain 𝐻 as a subgraph.
In this book, by 𝐻-free we always mean forbidding 𝐻 as a subgraph, rather than as

an induced subgraph. (See Notation and Conventions at the beginning of the book for the
distinction.)
Question 1.0.3 (Turán problem)

Determine ex(𝑛, 𝐻). Given a graph 𝐻, how does ex(𝑛, 𝐻) grow as 𝑛 → ∞?
The Turán problem is one of the most basic problems in extremal graph theory. It is named
after Pál Turán for his fundamental work on the subject. Research on this problem has led to
many important techniques. We will see a fairly satisfactory answer to the Turán problem for
nonbipartite graphs 𝐻. We also know the answer for a small number of bipartite graphs 𝐻.
However, for nearly all bipartite graphs 𝐻, much mystery remains.
In the first part of the chapter, we focus on techniques for upper bounding ex(𝑛, 𝐻). In
11
12 Forbidding a Subgraph
the last few sections, we turn our attention to lower bounding ex(𝑛, 𝐻) when 𝐻 is a bipartite
graph.
1.1 Forbidding a Triangle: Mantel’s Theorem

We begin by answering Question 1.0.1: what is the maximum number of edges in an 𝑛-vertex
triangle-free graph? This question was answered in the early 1900’s by Willem Mantel,
whose theorem is considered the starting point of extremal graph theory.
Let us partition the 𝑛 vertices into two equal halves (differing by one if 𝑛 is odd), and then
put in all edges across the two parts. This is the complete bipartite graph 𝐾 ⌊𝑛/2⌋,⌈𝑛/2⌉ , and is
triangle-free. For example,
𝐾4,4 = .
The graph 𝐾 ⌊𝑛/2⌋,⌈𝑛/2⌉ has ⌊𝑛/2⌋ ⌈𝑛/2⌉ = ⌊𝑛2 /4⌋ edges (one can check this equality by
separately considering even and odd 𝑛).
Mantel (1907) proved that 𝐾 ⌊𝑛/2⌋,⌈𝑛/2⌉ has the greatest number of edges among all triangle-
free graphs.
Theorem 1.1.1 (Mantel’s theorem)

Every 𝑛-vertex triangle-free graph has at most ⌊𝑛2 /4⌋ edges.
Using the notation of Definition 1.0.2, Mantel’s theorem says that

2
𝑛
ex(𝑛, 𝐾3 ) = .
4
Moreover, we will see that 𝐾 ⌊𝑛/2⌋,⌈𝑛/2⌉ is the unique maximizer of the number of edges among
𝑛-vertex triangle-free graphs.
We give two different proofs of Mantel’s theorem, each illustrating a different technique.
First proof of Mantel’s theorem. Let 𝐺 = (𝑉, 𝐸) be a triangle-free graph with |𝑉 | = 𝑛
vertices and |𝐸 | = 𝑚 edges. For every edge 𝑥𝑦 of 𝐺, note that 𝑥 and 𝑦 have no common
neighbors or else it would create a triangle.
𝑥 𝑦
𝑁 (𝑥) 𝑁 (𝑦)
Therefore, deg 𝑥 + deg 𝑦 ≤ 𝑛, which implies that

∑︁
(deg 𝑥 + deg 𝑦) ≤ 𝑚𝑛.
𝑥 𝑦 ∈𝐸
On the other hand, note that for each vertex 𝑥, the term deg 𝑥 appears once in the preceding
1.1 Forbidding a Triangle: Mantel’s Theorem 13
sum for each edge incident to 𝑥, and so it appears a total of deg 𝑥 times. We then apply the
Cauchy–Schwarz inequality to get
!2
∑︁ ∑︁ 1 ∑︁ (2𝑚) 2
(deg 𝑥 + deg 𝑦) = (deg 𝑥) 2 ≥ deg 𝑥 = .
𝑥 𝑦 ∈𝐸 𝑥 ∈𝑉
𝑛 𝑥 ∈𝑉 𝑛
Comparing the two inequalities, we obtain (2𝑚) 2 /𝑛 ≤ 𝑚𝑛, and hence 𝑚 ≤ 𝑛2 /4. Since 𝑚 is
an integer, we obtain 𝑚 ≤ ⌊𝑛2 /4⌋, as claimed. □
Second proof of Mantel’s theorem. Let 𝐺 = (𝑉, 𝐸) be a triangle-free graph. Let 𝑣 be a
vertex of maximum degree in 𝐺. Since 𝐺 is triangle-free, the neighborhood 𝑁 (𝑣) of 𝑣 is an
independent set.
𝐴 = 𝑁 (𝑣) 𝐵
(independent
set)
Partition 𝑉 = 𝐴 ∪ 𝐵 where 𝐴 = 𝑁 (𝑣) and 𝐵 = 𝑉 \ 𝐴. Since 𝑣 is a vertex of maximum

degree, we have deg 𝑥 ≤ deg 𝑣 = | 𝐴| for all 𝑥 ∈ 𝑉. Since 𝐴 contains no edges, every edge of
𝐺 has at least one endpoint in 𝐵. Therefore,
∑︁ 2
| 𝐴| + |𝐵| 𝑛2
|𝐸 | ≤ deg 𝑥 ≤ |𝐵| max deg 𝑥 ≤ | 𝐴| |𝐵| ≤ = , (1.1)
𝑥∈𝐵
𝑥∈𝐵 2 4
as claimed. □
Remark 1.1.2 (The equality case in Mantel’s theorem). The second proof just presented
shows that every 𝑛-vertex triangle-free graph with exactly ⌊𝑛2 /4⌋ edges must be isomorphic
Í
to 𝐾 ⌊𝑛/2⌋,⌈𝑛/2⌉ . Indeed, in (1.1), the inequality |𝐸 | ≤ 𝑥 ∈ 𝐵 deg 𝑥 is tight only if 𝐵 is an
Í
independent set, the inequality 𝑥 ∈ 𝐵 deg 𝑥 ≤ | 𝐴| |𝐵| is tight if 𝐵 is complete to 𝐴, and
| 𝐴| |𝐵| < ⌊𝑛2 /4⌋ unless | 𝐴| = |𝐵| (if 𝑛 is even) or || 𝐴| − |𝐵|| = 1 (if 𝑛 is odd).
(Exercise: also deduce the equality case from the first proof.)
In general, it is a good idea to keep the equality case in mind when following the proofs,
or when coming up with your own proofs, to make sure you are not giving away too much at
any step.
The next exercise can be solved by a neat application of Mantel’s theorem.

Exercise 1.1.3. Let 𝑋 and 𝑌 be independent and identically distributed random vectors
in R𝑑 according to some arbitrary probability distribution. Prove that
1
P(|𝑋 + 𝑌 | ≥ 1) ≥ P(|𝑋 | ≥ 1) 2 .
2
Hint: Consider i.i.d. 𝑋1 , . . . , 𝑋𝑛 , and then let 𝑛 → ∞.
The next several exercises explore extensions of Mantel’s theorem. It is useful to revisit
the proof techniques.
Exercise 1.1.4 (Many triangles). Show that a graph with 𝑛 vertices and 𝑚 edges has at
least
4𝑚 𝑛2
𝑚− triangles.
3𝑛 4
Exercise 1.1.5. Prove that every 𝑛-vertex nonbipartite triangle-free graph has at most
(𝑛 − 1) 2 /4 + 1 edges.
Exercise 1.1.6 (Stability). Let 𝐺 be an 𝑛-vertex triangle-free graph with at least ⌊𝑛2 /4⌋ − 𝑘
edges. Prove that 𝐺 can be made bipartite by removing at most 𝑘 edges.
Exercise 1.1.7. Show that every 𝑛-vertex triangle-free graph with minimum degree
greater than 2𝑛/5 is bipartite.
Exercise 1.1.8∗. Prove that every 𝑛-vertex graph with at least ⌊𝑛2 /4⌋ + 1 edges contains
at least ⌊𝑛/2⌋ triangles.
Exercise 1.1.9∗. Let 𝐺 be an 𝑛-vertex graph with ⌊𝑛2 /4⌋ − 𝑘 edges (here 𝑘 ∈ Z) and 𝑡
triangles. Prove that 𝐺 can be made bipartite by removing at most 𝑘 + 6𝑡/𝑛 edges, and that
this constant 6 is the best possible.
Exercise 1.1.10∗. Prove that every 𝑛-vertex graph with at least ⌊𝑛2 /4⌋ + 1 edges contains
some edge in at least (1/6 − 𝑜(1))𝑛 triangles, and that this constant 1/6 is the best possible.
1.2 Forbidding a Clique: Turán’s Theorem

We generalize Mantel’s theorem from triangles to cliques.
Question 1.2.1 (𝐾𝑟+1 -free graph)

What is the maximum number of edges in a 𝐾𝑟+1 -free graph on 𝑛 vertices?
Construction 1.2.2 (Turán graph)

The Turán graph 𝑻𝒏,𝒓 is defined to be the complete 𝑛-vertex 𝑟-partite graph with part
sizes differing by at most 1 (so each part has size ⌊𝑛/𝑟⌋ or ⌈𝑛/𝑟⌉).
Example 1.2.3. 𝑇10,3 = 𝐾3,3,4 :

1.2 Forbidding a Clique: Turán’s Theorem 15
Turán (1941) proved the following fundamental result.
Theorem 1.2.4 (Turán’s theorem)

The Turán graph 𝑇𝑛,𝑟 maximizes the number of edges among all 𝑛-vertex 𝐾𝑟+1 -free
graphs. It is also the unique maximizer.
The first part of the theorem says that

ex(𝑛, 𝐾𝑟+1 ) = 𝑒(𝑇𝑛,𝑟 ).
It is not too hard to give a precise formula for 𝑒(𝑇𝑛,𝑟 ), though there is a small, annoying
dependence on the residue class of 𝑛 mod 𝑟. The following bound is good enough for most
purposes.
Exercise 1.2.5. Show that

1 𝑛2
𝑒(𝑇𝑛,𝑟 ) ≤ 1 − ,
𝑟 2
with equality if and only if 𝑛 is divisible by 𝑟.
Corollary 1.2.6 (Turán’s theorem)

1 𝑛2
ex(𝑛, 𝐾𝑟+1 ) ≤ 1 − .
𝑟 2
Even when 𝑛 is not divisible by 𝑟, the difference between 𝑒(𝑇𝑛,𝑟 ) and (1 − 1/𝑟)𝑛2 /2 is
𝑂 (𝑛𝑟). As we are generally interested in the regime when 𝑟 is fixed, this difference is a
negligible lower-order contribution. That is,
2
1 𝑛
ex(𝑛, 𝐾𝑟+1 ) = 1 − − 𝑜(1) , for fixed 𝑟 as 𝑛 → ∞.
𝑟 2
Every 𝑟-partite graph is automatically 𝐾𝑟+1 -free. Let us first consider an easy special case
of the problem.
Lemma 1.2.7 (Maximum number of edges in an 𝑟 -partite graph)

Among 𝑛-vertex 𝑟-partite graphs, 𝑇𝑛,𝑟 is the unique graph with the maximum number of
edges.
Proof. Suppose we have an 𝑛-vertex 𝑟-partite graph with the maximum possible number of
edges. It should be a complete 𝑟-partite graph. If there were two vertex parts 𝐴 and 𝐵 with
| 𝐴| + 2 ≤ |𝐵|, then moving a vertex from 𝐵 (the larger part) to 𝐴 (the smaller part) would
increase the number of edges by (| 𝐴| + 1) (|𝐵| − 1) − | 𝐴| |𝐵| = |𝐵| − | 𝐴| − 1 > 0. Thus all
the vertex parts must have sizes within one of each other. The Turán graph 𝑇𝑛,𝑟 is the unique
such graph. □
We will see three proofs of Turán’s theorem. The first proof extends our second proof of
Mantel’s theorem.
First proof of Turán’s theorem. We prove by induction on 𝑟. The case 𝑟 = 1 is trivial, as a
𝐾2 -free graph is empty. Now assume 𝑟 > 1 and that ex(𝑛, 𝐾𝑟 ) = 𝑒(𝑇𝑛,𝑟 −1 ) for every 𝑛.
Let 𝐺 = (𝑉, 𝐸) be a 𝐾𝑟+1 -free graph. Let 𝑣 be a vertex of maximum degree in 𝐺. Since 𝐺
is 𝐾𝑟+1 -free, the neighborhood 𝐴 = 𝑁 (𝑣) of 𝑣 is 𝐾𝑟 -free. So, by the induction hypothesis,
𝑒( 𝐴) ≤ ex(| 𝐴| , 𝐾𝑟 ) = 𝑒(𝑇| 𝐴|,𝑟 −1 ).
𝐴 𝐵
(𝐾𝑟 -free)
Let 𝐵 = 𝑉 \ 𝐴. Since 𝑣 is a vertex of maximum degree, we have deg 𝑥 ≤ deg 𝑣 = | 𝐴| for

all 𝑥 ∈ 𝑉. So, the number of edges with at least one vertex in 𝐵 is
∑︁
𝑒( 𝐴, 𝐵) + 𝑒(𝐵) ≤ deg 𝑥 ≤ |𝐵| max deg 𝑥 ≤ | 𝐴| |𝐵| .
𝑥∈𝐵
𝑥∈𝐵
Thus
𝑒(𝐺) = 𝑒( 𝐴) + 𝑒( 𝐴, 𝐵) + 𝑒(𝐵) ≤ 𝑒(𝑇| 𝐴|,𝑟 −1 ) + | 𝐴| |𝐵| ≤ 𝑒(𝑇𝑛,𝑟 ),
where the final step follows from the observation that 𝑒(𝑇| 𝐴|,𝑟 −1 ) + | 𝐴| |𝐵| is the number of
edges in an 𝑛-vertex 𝑟-partite graph (with part of size |𝐵| and the remaining vertices equitably
partitioned into 𝑟 − 1 parts) and Lemma 1.2.7.
To have equality in each of the preceding steps, 𝐵 must be an independent set (or else
Í
𝑦 ∈ 𝐵 deg(𝑦) < | 𝐴| |𝐵|) and 𝐴 must induce 𝑇| 𝐴|,𝑟 −1 , so that 𝐺 is 𝑟-partite. We knew from
Lemma 1.2.7 that the Turán graph 𝑇𝑛,𝑟 uniquely maximizes the number of edges among
𝑟-partite graphs. □
The second proof starts out similarly to our first proof of Mantel’s theorem. Recall that in
Mantel’s theorem, the initial observation was that in a triangle-free graph, given an edge, its
two endpoints must have no common neighbors (or else they form a triangle). Generalizing,
in a 𝐾4 -free graph, given a triangle, its three vertices have no common neighbor. The rest of
the proof proceeds somewhat differently from earlier. Instead of summing over all edges as
we did before, we remove the triangle and apply induction to the rest of the graph.
Second proof of Turán’s theorem. We fix 𝑟 and proceed by induction on 𝑛. The statement
is trivial for 𝑛 ≤ 𝑟, as the Turán graph is the complete graph 𝐾𝑛 = 𝑇𝑛,𝑟 and thus maximizes
the number of edges.
Now, assume that 𝑛 > 𝑟 and that Turán’s theorem holds for all graphs on fewer than 𝑛
1.2 Forbidding a Clique: Turán’s Theorem 17
vertices. Let 𝐺 = (𝑉, 𝐸) be an 𝑛-vertex 𝐾𝑟+1 -free graph with the maximum possible number
of edges. By the maximality assumption, 𝐺 contains 𝐾𝑟 as a subgraph, since otherwise we
could add an edge to 𝐺 and it would still be 𝐾𝑟+1 -free. Let 𝐴 be the vertex set of an 𝑟-clique
in 𝐺, and let 𝐵 B 𝑉 \ 𝐴.
𝐴
(𝑟 = 3)
Since 𝐺 is 𝐾𝑟+1 -free, every 𝑥 ∈ 𝐵 has at most 𝑟 − 1 neighbors in 𝐴. So

∑︁ ∑︁
𝑒( 𝐴, 𝐵) = deg(𝑦, 𝐴) ≤ (𝑟 − 1) = (𝑟 − 1) (𝑛 − 𝑟).
𝑦∈𝐵 𝑦∈𝐵
We have
𝑒(𝐺) = 𝑒( 𝐴) + 𝑒( 𝐴, 𝐵) + 𝑒(𝐵)

𝑟
≤ + (𝑟 − 1) (𝑛 − 𝑟) + 𝑒(𝑇𝑛−𝑟 ,𝑟 ) = 𝑒(𝑇𝑛,𝑟 ),
2
where the inequality uses the induction hypothesis on 𝐺 [𝐵], which is 𝐾𝑟+1 -free, and the final
equality can be seen by removing a 𝐾𝑟 from 𝑇𝑛,𝑟 .
Finally, let us check when equality occurs. To have equality in each of thepreceding steps,
the subgraph induced on 𝐵 must be 𝑇𝑛−𝑟 ,𝑟 by induction. To have 𝑒( 𝐴) = 𝑟2 , 𝐴 must induce
a clique. To have 𝑒( 𝐴, 𝐵) = (𝑟 − 1) (𝑛 − 𝑟), every vertex of 𝐵 must be adjacent to all but one
vertex in 𝐴. Also, two vertices 𝑥, 𝑦 lying in distinct parts of 𝐺 [𝐵] 𝑇𝑛−𝑟 ,𝑟 cannot “miss” the
same vertex 𝑣 of 𝐴, or else 𝐴 ∪ {𝑥, 𝑦} \ {𝑣} would be an 𝐾𝑟+1 -clique. This then forces 𝐺 to
be 𝑇𝑛,𝑟 . □
The third proof uses a method known as Zykov symmetrization. The idea here is that
if a 𝐾𝑟+1 -free graph that is a not a Turán graph, then we should be able make some local
modifications (namely replacing a vertex by a clone of another vertex) to get another 𝐾𝑟+1 -free
with strictly more edges.
Third proof of Turán’s theorem. As before, let 𝐺 be an 𝑛-vertex 𝐾𝑟+1 -free graph with the
maximum possible number of edges.
We claim that if 𝑥 and 𝑦 are nonadjacent vertices, then deg 𝑥 = deg 𝑦. Indeed, suppose
deg 𝑥 > deg 𝑦. We can modify 𝐺 by removing 𝑦 and adding in a clone of 𝑥 (a new vertex 𝑥 ′
with the same neighborhood as 𝑥 but not adjacent to 𝑥), as illustrated below.
𝑥 𝑦 𝑥 𝑥′
−→
The resulting graph would still be 𝐾𝑟+1 -free (since a clique cannot contain both 𝑥 and its
clone) and has strictly more edges than 𝐺, thereby contradicting the assumption that 𝐺 has
the maximum possible number of edges.
Suppose 𝑥 is nonadjacent to both 𝑦 and 𝑧 in 𝐺. We claim that 𝑦 and 𝑧 must be nonadjacent.
We just saw that deg 𝑥 = deg 𝑦 = deg 𝑧. If 𝑦𝑧 is an edge, then by deleting 𝑦 and 𝑧 from 𝐺 and
adding two clones of 𝑥, we obtain a 𝐾𝑟+1 -free graph with one more edge than 𝐺. This would
contradict the maximality of 𝐺.
𝑥 𝑥
−→
𝑦 𝑧 𝑥′ 𝑥 ′′
Therefore, nonadjacency is an equivalence relation among vertices of 𝐺. So the comple-

ment of 𝐺 is a union of cliques. Hence 𝐺 is a complete multipartite graph, which has at
most 𝑟 parts since 𝐺 is 𝐾𝑟+1 -free. Among all complete 𝑟-partite graphs, the Turán graph 𝑇𝑛,𝑟
is the unique graph that maximizes the number of edges, by Lemma 1.2.7. Therefore, 𝐺 is
isomorphic to 𝑇𝑛,𝑟 . □
The last proof we give in this section uses the probabilistic method. This probabilistic
proof was given in the book The Probabilistic Method by Alon and Spencer, though the key
inequality is due earlier to Caro and Wei. Below, we prove Turán’s theorem in the formulation
of Corollary 1.2.6, i.e, ex(𝑛, 𝐾𝑟+1 ) ≤ (1 − 1/𝑟)𝑛2 /2. A more careful analysis of the proof can
yield the stronger statement of Theorem 1.2.4, which we omit.
Fourth proof of Turán’s theorem (Corollary 1.2.6). Let 𝐺 = (𝑉, 𝐸) be an 𝑛-vertex, 𝐾𝑟+1 -
free graph. Consider a uniform random ordering of the vertices. Let
𝑋 = {𝑣 ∈ 𝑉 : 𝑣 is adjacent to all earlier vertices in the random ordering}.
Then 𝑋 is a clique. Since the ordering was chosen uniformly at random,
1
P(𝑣 ∈ 𝑋) = P(𝑣 appears before all its nonneighbors) = .
𝑛 − deg 𝑣
Since 𝐺 is 𝐾𝑟+1 -free, |𝑋 | ≤ 𝑟. So by linearity of expectations
∑︁
𝑟 ≥ E |𝑋 | = P(𝑣 ∈ 𝑋)
∑︁
𝑣 ∈𝑉
1 𝑛 𝑛
= ≥ Í = .
𝑣 ∈𝑉
𝑛 − deg 𝑣 𝑛 − ( 𝑣 ∈𝑉 deg 𝑣)/𝑛 𝑛 − 2𝑚/𝑛
Rearranging gives

1 𝑛2
𝑚 ≤ 1− . □
𝑟 2
In Chapter 5, we will see another proof of Turán’s theorem using a method known as
graph Lagrangians.
1.3 Turán Density and Supersaturation 19
Exercise 1.2.8. Let 𝐺 be a 𝐾𝑟+1 -free graph. Prove that there exists an 𝑟-partite graph 𝐻
on the same vertex set as 𝐺 such that deg𝐻 (𝑥) ≥ deg𝐺 (𝑥) for every vertex 𝑥 (here deg𝐻 (𝑥)
is the degree of 𝑥 in 𝐻, and likewise with deg𝐺 (𝑥) for 𝐺). Give another proof of Turán’s
theorem from this fact.
The following exercise is an extension of Exercise 1.1.6.
Exercise 1.2.9∗ (Stability). Let 𝐺 be an 𝑛-vertex 𝐾𝑟+1 -free graph with at least 𝑒(𝑇𝑛,𝑟 ) − 𝑘
edges, where 𝑇𝑛,𝑟 is the Turán graph. Prove that 𝐺 can be made 𝑟-partite by removing at
most 𝑘 edges.
The next exercise is a neat geometric application of Turán’s theorem.
Exercise 1.2.10. Let 𝑆 be a set of 𝑛 points in the plane, with the property that no two
points are at distance greater
√ than 1. Show that 𝑆 has at most ⌊𝑛2 /3⌋ pairs of points at
distance greater than 1/ 2. Also, show that the bound ⌊𝑛2 /3⌋ is tight (i.e., cannot be
improved).
1.3 Turán Density and Supersaturation

Turán’s theorem exactly determines ex(𝑛, 𝐻) when 𝐻 is a clique. Such precise answers are
actually quite rare in extremal graph theory. We are often content with looser bounds and
asymptotics.
We will go on to bound ex(𝑛, 𝐻) for other values of 𝐻. But for now, let us take a short
detour and think about the structure of the problem.
Turán Density
In this chapter, we will define the edge density of a graph 𝐺 to be

𝑣(𝐺)
𝑒(𝐺) .
2
So the edge density of a clique is 1. Later in the book, we will consider a different normal-
ization 2𝑒(𝐺)/𝑣(𝐺) 2 for edge density, which is more convenient for other purposes. When
𝑣(𝐺) is large, there is no significant difference between the two choices.
Next, we use an averaging/sampling argument to show that ex(𝑛, 𝐻)/ 𝑛2 is nonincreasing
in 𝑛.
Proposition 1.3.1 (Monotonicity of Turán numbers)
For every graph 𝐻 and positive integer 𝑛,
ex(𝑛 + 1, 𝐻) ex(𝑛, 𝐻)
𝑛+1
≤ 𝑛 .
2 2
Proof. Let 𝐺 be an 𝐻-free graph on 𝑛 + 1 vertices. For each 𝑛-vertex subset 𝑆 of 𝑉 (𝐺), since
𝐺 [𝑆] is also 𝐻-free, we have
𝑒(𝐺 [𝑆]) ex(𝑛, 𝐻)
𝑛 ≤ 𝑛 .
2 2
Varying 𝑆 uniformly over all 𝑛-vertex subsets of 𝑉 (𝐺), the left-hand side averages to the
edge density of 𝐺 by linearity of expectations. (Check this.) It follows that
𝑒(𝐺) ex(𝑛, 𝐻)
𝑛+1
≤ 𝑛 .
2 2
The claim then follows. □

𝑛
For every fixed 𝐻, the sequence ex(𝑛, 𝐻)/ 2
is nonincreasing and bounded between 0
and 1. It follows that it approaches a limit.
Definition 1.3.2 (Turán density)

The Turán density of a graph 𝐻 is defined to be
ex(𝑛, 𝐻)
𝝅(𝑯) B lim
𝑛→∞ 𝑛 .
2
Here are some additional equivalent definitions of Turán density:

• 𝜋(𝐻) is smallest real number so that for every 𝜀 > 0 there is some 𝑛0 = 𝑛0 (𝐻, 𝜀) so
that for every 𝑛 ≥ 𝑛0 , every 𝑛-vertex graph with at least (𝜋(𝐻) + 𝜀) 𝑛2 edges contains
𝐻 as a subgraph;
• 𝜋(𝐻) is the smallest real number so that every 𝑛-vertex 𝐻-free graph has edge density
≤ 𝜋(𝐻) + 𝑜(1).
Recall, from Turán’s theorem, that
2
1 𝑛
ex(𝑛, 𝐾𝑟+1 ) = 1 − − 𝑜(1) , for fixed 𝑟 as 𝑛 → ∞,
𝑟 2
which is equivalent to
1
𝜋(𝐾𝑟+1 ) = 1 − .
𝑟
In the next couple of sections we will prove the Erdős–Stone–Simonovits theorem, which
determines the Turán density for every graph 𝐻:
1
𝜋(𝐻) = 1 − ,
𝜒(𝐻) − 1
where 𝜒(𝐻) is the chromatic number of 𝐻. It should be surprising that the Turán density of
𝐻 depends only on the chromatic number of 𝐻.
With the Erdős–Stone–Simonovits theorem, it may seem as if the Turán problem is essen-
tially understood, but actually this would be very far from the truth. We will see in the next
section that 𝜋(𝐻) = 0 for every bipartite graph 𝐻. In other words ex(𝑛, 𝐻) = 𝑜(𝑛2 ). Actual
asymptotics growth rate of ex(𝑛, 𝐻) is often unknown.
In a different direction, the generalization to hypergraphs, while looking deceptively
similar, turns out to be much more difficult, and very little is known here.
Remark 1.3.3 (Hypergraph Turán problem). Generalizing from graphs to hypergraphs,
given an 𝑟-uniform hypergraph 𝐻, we write ex(𝑛, 𝐻) for the maximum number of edges in
an 𝑛-vertex 𝑟-uniform hypergraph that does not contain 𝐻 as a subgraph. A straightforward
1.3 Turán Density and Supersaturation 21

extension of Proposition 1.3.1 gives that ex(𝑛, 𝐻)/ 𝑛𝑟 is a nonincreasing function of 𝑛, for
each fixed 𝐻. So we can similarly define the hypergraph Turán density
ex(𝑛, 𝐻)
𝜋(𝐻) B lim
𝑛→∞ 𝑛 .
𝑟
The exact value of 𝜋(𝐻) is known in very few cases. It is a major open problem to determine
𝜋(𝐻) when 𝐻 is the complete 3-uniform hypergraph on four vertices (also known as a
tetrahedron), and more generally when 𝐻 is a complete hypergraph.
Supersaturation
We know from Mantel’s theorem that any 𝑛-vertex graph 𝐺 with > 𝑛2 /4 edges must contain
a triangle. What if 𝐺 has a lot more edges? It turns out that 𝐺 must have a lot of triangles.
In particular, an 𝑛-vertex graph with > (1/4 + 𝜀)𝑛2 edges must have at least 𝛿𝑛3 triangles
for some constant 𝛿 > 0 depending on 𝜀 > 0. This is indeed a lot of triangles, since there
are could only be at most 𝑂 (𝑛3 ) triangles no matter what. (Exercise 1.1.4 asks you to give a
more precise quantitative lower bound on the number of triangles. The optimal dependence
of 𝛿 on 𝜀 is a difficult problem that we will discuss in Chapter 5.)
It turns out there is a general phenomenon in combinatorics where once some density
crosses an existence threshold (e.g., the Turán density is the threshold for 𝐻-freeness), it
will be possible to find not just one copy of the desired object, but in fact lots and lots of
copies. This fundamental principle, called supersaturation, is useful for many applications,
including in our upcoming determination of 𝜋(𝐻) for general 𝐻.
Theorem 1.3.4 (Supersaturation)

For every 𝜀 > 0 and graph 𝐻 there exist some 𝛿 > 0 and 𝑛0 such that every graph on
𝑛 ≥ 𝑛0 vertices with at least (𝜋(𝐻) + 𝜀) 𝑛2 edges contains at least 𝛿𝑛𝑣 (𝐻 ) copies of 𝐻 as
a subgraph.
Equivalently: every 𝑛-vertex graph with 𝑜(𝑛𝑣 (𝐻 ) ) copies of 𝐻 has edge density ≤ 𝜋(𝐻) +
𝑜(1) (here 𝐻 is fixed). The sampling argument in the following proof is useful in many
applications.
Proof. By the definition of the Turán density, there exists some 𝑛0 (depending on 𝐻 and

𝜀) such that every 𝑛0 -vertex graph with at least (𝜋(𝐻) + 𝜀/2) 𝑛20 edges contains 𝐻 as a
subgraph.
Let 𝑛 ≥ 𝑛0 and 𝐺 be an 𝑛-vertex graph with at least (𝜋(𝐻) + 𝜀) 𝑛2 edges. Let 𝑆 be an
𝑛0 -element subset of 𝑉 (𝐺), chosen uniformly at random. Let 𝑋 denote the edge density
of 𝐺 [𝑆]. By averaging, E𝑋 equals the edge density of 𝐺, and so E𝑋 ≥ 𝜋(𝐻) + 𝜀. Then
𝑋 ≥ 𝜋(𝐻) + 𝜀/2 with probability ≥ 𝜀/2 (or else E𝑋 could not be as large as 𝜋(𝐻) + 𝜀). So,
from the previous paragraph, we know that with probability ≥ 𝜀/2, 𝐺 [𝑆] contains a copy of
(𝐻 )
𝐻. This gives us ≥ (𝜀/2) 𝑛𝑛0 copies of 𝐻, but each copy of 𝐻 may be counted up to 𝑛𝑛−𝑣
0 −𝑣 (𝐻 )
times. Thus, the number of copies of 𝐻 in 𝐺 is

(𝜀/2) 𝑛𝑛0
≥ 𝑛−𝑣 (𝐻 ) = Ω𝐻, 𝜀 (𝑛𝑣 (𝐻 ) ). □
𝑛0 −𝑣 (𝐻 )
Exercise 1.3.5 (Supersaturation for hypergraphs). Let 𝐻 be an 𝑟-uniform hypergraph

with hypergraph Turán density 𝜋(𝐻). Prove that every 𝑛-vertex 𝑟-uniform hypergraph with
𝑜(𝑛𝑣 (𝐻 ) ) copies of 𝐻 has at most (𝜋(𝐻) + 𝑜(1)) 𝑛𝑟 edges.
Exercise 1.3.6 (Density Ramsey). Prove that for every 𝑠 and 𝑟, there is some constant
𝑐 > 0 so that for every sufficiently large 𝑛, if the edges of 𝐾𝑛 are colored using 𝑟 colors,
then at least 𝑐 fraction of all copies of 𝐾𝑠 are monochromatic.
Exercise 1.3.7 (Density Szemerédi). Let 𝑘 ≥ 3. Assuming Szemerédi’s theorem for

𝑘-term arithmetic progressions (i.e., every subset of [𝑁] without a 𝑘-term arithmetic
progression has size 𝑜(𝑁)), prove the following density version of Szemerédi’s theorem:
For every 𝛿 > 0 there exist 𝑐 > 0 and 𝑁0 (both depending only on 𝑘 and 𝛿) such that for
every 𝐴 ⊆ [𝑁] with | 𝐴| ≥ 𝛿𝑁 and 𝑁 ≥ 𝑁0 , the number of 𝑘-term arithmetic progressions
in 𝐴 is at least 𝑐𝑁 2 .
1.4 Forbidding a Complete Bipartite Graph: Kővári–Sós–Turán Theorem

In this section, we provide an upper bound on ex(𝑛, 𝐾𝑠,𝑡 ), the maximum number of edges in
an 𝑛-vertex 𝐾𝑠,𝑡 -free graph. It is a major open problem to determine the asymptotic growth
of ex(𝑛, 𝐾𝑠,𝑡 ). For certain pairs (𝑠, 𝑡) the answer is known, as we will discuss later in the
chapter.
Problem 1.4.1 (Zarankiewicz problem)

Determine ex(𝑛, 𝐾𝑠,𝑡 ), the maximum number of edges in an 𝑛-vertex 𝐾𝑠,𝑡 -free graph.
Zarankiewicz (1951) originally asked a related problem: determine the maximum number
of 1s in an 𝑚 × 𝑛 matrix without an 𝑠 × 𝑡 submatrix with all entries 1.
The main theorem of this section is the fundamental result due to Kővári, Sós, and Turán
(1954). We will refer to it as the KST theorem, which stands both for its discoverers, as well
as for the forbidden subgraph 𝐾𝑠,𝑡 .
Theorem 1.4.2 (Kővári–Sós–Turán theorem – “KST theorem”)

For positive integers 𝑠 ≤ 𝑡, there exists some constant 𝐶 = 𝐶 (𝑠, 𝑡), such that, for all 𝑛,
ex(𝑛, 𝐾𝑠,𝑡 ) ≤ 𝐶𝑛2−1/𝑠 .
The proof proceeds by double counting.

Proof. Let 𝐺 be an 𝑛-vertex 𝐾 𝑠,𝑡 -free graph with 𝑚 edges. Let
..
𝑋 = number of copies of 𝐾𝑠,1 in 𝐺. .
(When 𝑠 = 1, we set 𝑋 = 2𝑒(𝐺).) The strategy is to count 𝑋 in two ways. First we count 𝐾𝑠,1
by first embedding the “left” 𝑠 vertices of 𝐾𝑠,1 . Then we count 𝐾𝑠,1 by first embedding the
“right” single vertex of 𝐾𝑠,1 .
1.4 Forbidding a Complete Bipartite Graph: Kővári–Sós–Turán Theorem 23
Upper bound on 𝑋. Since 𝐺 is 𝐾𝑠,𝑡 -free, every 𝑠-vertex subset of 𝐺 has ≤ 𝑡 − 1 common
neighbors. Therefore,

𝑛
𝑋≤ (𝑡 − 1).
𝑠

Lower bound on 𝑋. For each vertex 𝑣 of 𝐺, there are exactly deg𝑠 𝑣 ways to pick 𝑠 of its
neighbors to form a 𝐾𝑠,1 as a subgraph. Therefore
∑︁ deg 𝑣
𝑋= .
𝑣 ∈𝑉 (𝐺)
𝑠
To obtain a lower bound onthis quantity in terms of the number of edges 𝑚 of 𝐺, we use a
standard trick of viewing 𝑥𝑠 as a convex function on the reals, namely, letting
(
𝑥(𝑥 − 1) · · · (𝑥 − 𝑠 + 1)/𝑠! if 𝑥 ≥ 𝑠 − 1
𝑓𝑠 (𝑥) =
0 𝑥 < 𝑠 − 1.

Then 𝑓𝑠 (𝑥) = 𝑥𝑠 for all nonnegative integers 𝑥. Furthermore 𝑓𝑠 is a convex function. Since
the average degree of 𝐺 is 2𝑚/𝑛, it follows by convexity that
∑︁
2𝑚
𝑋= 𝑓𝑠 (deg 𝑣) ≥ 𝑛 𝑓𝑠 .
𝑣 ∈𝑉 (𝐺)
𝑛

(It would be a sloppy mistake to lower bound 𝑋 by 𝑛 2𝑚/𝑛
𝑠
.)
Combining the upper bound and the lower bound. We find that

2𝑚 𝑛
𝑛 𝑓𝑠 ≤𝑋≤ (𝑡 − 1).
𝑛 𝑠
Since 𝑓𝑠 (𝑥) = (1 + 𝑜(1))𝑥 𝑠 /𝑠! for 𝑥 → ∞ and fixed 𝑠, we find that, as 𝑛 → ∞,
𝑠
𝑛 2𝑚 𝑛𝑠
≤ (1 + 𝑜(1)) (𝑡 − 1).
𝑠! 𝑛 𝑠!
Therefore,

(𝑡 − 1) 1/𝑠
𝑚≤ + 𝑜(1) 𝑛2−1/𝑠 . □
2
The final bound in the proof gives us a somewhat more precise estimate than stated in
Theorem 1.4.2. Let us record it here for future reference.
Theorem 1.4.3 (KST theorem)

Fix positive integers 𝑠 ≤ 𝑡. Then, as 𝑛 → ∞,

(𝑡 − 1) 1/𝑠
ex(𝑛, 𝐾𝑠,𝑡 ) ≤ + 𝑜(1) 𝑛2−1/𝑠 .
2
It has been long conjectured that the KST theorem is tight up to a constant factor.
Conjecture 1.4.4 (Tightness of KST bound)

For positive integers 𝑠 ≤ 𝑡, there exists a constant 𝑐 = 𝑐(𝑠, 𝑡) > 0 such that for all 𝑛 ≥ 2,
ex(𝑛, 𝐾𝑠,𝑡 ) ≥ 𝑐𝑛2−1/𝑠 .
(In other words, ex(𝑛, 𝐾𝑠,𝑡 ) = Θ𝑠,𝑡 (𝑛2−1/𝑠 ).)
In the final sections of this chapter, we will produce some constructions showing that
Conjecture 1.4.4 is true for 𝐾2,𝑡 and 𝐾3,𝑡 . We also know that the conjecture is true if 𝑡 is much
larger than 𝑠. The first open case of the conjecture is 𝐾4,4 .
Here is an easy consequence of the KST theorem.
Corollary 1.4.5
For every bipartite graph 𝐻, there exists some constant 𝑐 > 0 so that ex(𝑛, 𝐻) =
𝑂 𝐻 (𝑛2−𝑐 ).
Proof. Suppose the two vertex parts of 𝐻 have sizes 𝑠 and 𝑡, with 𝑠 ≤ 𝑡. Then 𝐻 ⊆ 𝐾 𝑠,𝑡 . And
thus every 𝑛-vertex 𝐻-free graph is also 𝐾𝑠,𝑡 -free, and thus has 𝑂 𝑠,𝑡 (𝑛2−1/𝑠 ) edges. □
In particular, the Turán density 𝜋(𝐻) of every bipartite graph 𝐻 is zero.
The KST theorem gives a constant 𝑐 in the preceding corollary that depends on the number
of vertices on the smaller part of 𝐻. In Section 1.7, we will use the dependent random choice
technique to give a proof of the corollary showing that 𝑐 only has to depend on the maximum
degree of 𝐻.
Geometric Applications of the KST Theorem

The following famous problem was posed by Erdős (1946).
Question 1.4.6 (Erdős unit distance problem)

What is the maximum number of unit distances formed by a set of 𝑛 points in R2 ?
In other words, given 𝑛 distinct points in the plane, at most how many pairs of these points
can be exactly distance 1 apart? We can draw a graph with these 𝑛 points as vertices, with
edges joining points exactly a unit distance apart.
To get a feeling for the problem, let us play with some constructions. For small values of
𝑛, it is not hard to check by hand that the following configurations are optimal.
𝑛= 3 4 5 6 7
What about for larger values of 𝑛? If we line up the 𝑛 points equally spaced on a line, we
get 𝑛 − 1 unit distances.
···
1.4 Forbidding a Complete Bipartite Graph: Kővári–Sós–Turán Theorem 25
We can be a bit more efficient by chaining up triangles. The following construction gives us
2𝑛 − 3 unit distances.
···
The construction for 𝑛 = 6 looks like it was obtained by copying and translating a unit
triangle. We can generalize this idea to obtain a recursive construction. Let 𝑓 (𝑛) denote the
maximum number of unit distances formed by 𝑛 points in the plane. Given a configuration
𝑃 with ⌊𝑛/2⌋ points that has 𝑓 (⌊𝑛/2⌋) unit distances, we can copy 𝑃 and translate it by a
generic unit vector to get 𝑃′ . The configuration 𝑃 ∪ 𝑃′ has at least 2 𝑓 ( ⌊𝑛/2⌋) + ⌊𝑛/2⌋ unit
distances. We can solve the recursion to get 𝑓 (𝑛) ≳ 𝑛 log 𝑛.
𝑃 𝑃′
1
Now we take a different approach to obtain an even better construction. Take a square grid
√ √
with ⌊ 𝑛⌋ × ⌊ 𝑛⌋ vertices. Instead of choosing the distance between adjacent points as the
√
unit distance, we can scale the configuration so that 𝑟 becomes the “unit” distance for some
integer 𝑟. As an illustration, here is an example of a 5 × 5 grid with 𝑟 = 10.
It turns out that by choosing the optimal 𝑟 as a function of 𝑛, we can get at least
𝑛1+𝑐/log log 𝑛
unit distances, where 𝑐 > 0 is some absolute constant. The proof uses analytic number theory,
which we omit as it would take us too far afield. The basic idea is to choose 𝑟 to be a product
of many distinct primes that are congruent to 1 modulo 4, so that 𝑟 can be represented as a
sum of two squares in many different ways, and then estimate the number of such ways.
It is conjectured that the last construction just discussed is close to optimal.
Conjecture 1.4.7 (Erdős unit distance conjecture)

Every set of 𝑛 points in R2 has at most 𝑛1+𝑜(1) unit distances.
The KST theorem can be used to prove the following upper bound on the number of unit
distances.
Theorem 1.4.8 (Upper bound on the unit distance problem)

Every set of 𝑛 points in R2 has 𝑂 (𝑛3/2 ) unit distances.
Proof. Every unit distance graph is 𝐾2,3 -free. Indeed, for every pair of distinct points, there
are at most two other points that are at a unit distance from both points.
𝑝 𝑞
So, the number of edges is at most ex(𝑛, 𝐾2,3 ) = 𝑂 (𝑛3/2 ) by Theorem 1.4.2. □
There is a short proof of a better bound of 𝑂 (𝑛4/3 ) using the crossing number inequality
(see Section 8.2), and this is best known upper bound to date.
Erdős (1946) also asked the following related question.
Question 1.4.9 (Erdős distinct distances problem)

What is the minimum number of distinct distances formed by 𝑛 points in R2 ?
Let 𝑔(𝑛) denote the answer. The asymptotically best construction for the minimum number
of distinct distances is also a square grid, same √︁
as earlier. It can be shown that a square grid
√ √
with ⌊ 𝑛⌋ × ⌊ 𝑛⌋ points has on the order of 𝑛/ log 𝑛 distinct distances. This is conjectured
√︁
to be optimal (i.e., 𝑔(𝑛) ≳ 𝑛/ log 𝑛).
Let 𝑓 (𝑛) denote the
maximum number of unit distances among 𝑛 points in the answer. We
have 𝑓 (𝑛)𝑔(𝑛) ≥ 𝑛2 , since each distance occurs at most 𝑓 (𝑛) times. So an upper bound on
𝑓 (𝑛) gives a lower bound on 𝑔(𝑛) (but not conversely).
A breakthrough on the distinct distances problem was obtained by Guth and Katz (2015).
Theorem 1.4.10 (Guth–Katz distinct distances theorem)

A set of 𝑛 points in R2 form Ω(𝑛/log 𝑛) distinct distances.
In other
√︁ words, 𝑔(𝑛) ≳ 𝑛/log 𝑛, thereby matching the upper bound example up to a factor
of 𝑂 ( log 𝑛). The Guth–Katz proof is quite sophisticated. It uses tools ranging from the
polynomial method to algebraic geometry.
Exercise 1.4.11. Show that a 𝐶4 -free bipartite graph between two vertex parts of sizes 𝑎
and 𝑏 has at most 𝑎𝑏 1/2 + 𝑏 edges.
Exercise 1.4.12 (Density KST). Prove that for every pair of positive integers 𝑠 ≤ 𝑡, there
𝑛
are constants 𝐶, 𝑐 > 0 such that every 𝑛-vertex graph with 𝑝 2
edges contains at least
𝑐 𝑝 𝑠𝑡 𝑛𝑠+𝑡 copies of 𝐾𝑠,𝑡 , provided that 𝑝 ≥ 𝐶𝑛 −1/𝑠 .
The next exercise asks you to think about the quantitative dependencies in the proof of the
KST theorem.
Exercise 1.4.13. Show that for every 𝜀 > 0, there exists 𝛿 > 0 such that every graph with
𝑛 vertices and at least 𝜀𝑛2 edges contains a copy of 𝐾𝑠,𝑡 where 𝑠 ≥ 𝛿 log 𝑛 and 𝑡 ≥ 𝑛0.99 .
The next exercise illustrates a bad definition of density of a subset of Z2 (it always ends
up being either 0 or 1).
Exercise 1.4.14 (How not to define density). Let 𝑆 ⊆ Z2 . Define
|𝑆 ∩ ( 𝐴 × 𝐵)|
𝑑 𝑘 (𝑆) = max .
𝐴,𝐵⊆Z | 𝐴| |𝐵|
| 𝐴|=| 𝐵|=𝑘
Show that lim 𝑘→∞ 𝑑 𝑘 (𝑆) exists and is always either 0 or 1.

1.5 Forbidding a General Subgraph: Erdős–Stone–Simonovits Theorem 27
1.5 Forbidding a General Subgraph: Erdős–Stone–Simonovits Theorem

Turán’s theorem tells us that
2
1 𝑛
ex(𝑛, 𝐾𝑟+1 ) = 1 − − 𝑜(1) for fixed 𝑟.
𝑟 2
The KST theorem implies that
ex(𝑛, 𝐻) = 𝑜(𝑛2 ) for any fixed bipartite graph 𝐻.
In this section, we extend these results and determine ex(𝑛, 𝐻), up to an 𝑜(𝑛2 ) error term,
for every graph 𝐻. In other words, we will compute the Turán density 𝜋(𝐻).
Initially it seems possible that the Turán density 𝜋(𝐻) might depend on 𝐻 in some
complicated way. It turns out that it only depends on the chromatic number 𝝌(𝑯) of 𝐻,
which is the smallest number of colors needed to color the vertices of 𝐻 such that no two
adjacent vertices receive the same color.
Suppose 𝜒(𝐻) = 𝑟. Then 𝐻 cannot be a subgraph of any (𝑟 −1)-partite graph. In particular,
the Turán graph 𝑇𝑛,𝑟 −1 is 𝐻-free. (Recall from Construction 1.2.2 that 𝑇𝑛,𝑟 −1 is the complete
(𝑟 − 1)-partite graph with 𝑛 vertices divided into nearly equal parts.) Therefore,
2
1 𝑛
ex(𝑛, 𝐻) ≥ 𝑒(𝑇𝑛,𝑟 −1 ) = 1 − + 𝑜(1) .
𝑟 −1 2
The main theorem of this section, which follows, is a matching upper bound.
Theorem 1.5.1 (Erdős–Stone–Simonovits theorem)

For every graph 𝐻, as 𝑛 → ∞,
2
1 𝑛
ex(𝑛, 𝐻) = 1 − + 𝑜(1) .
𝜒(𝐻) − 1 2
In other words, the Turán density of 𝐻 is
1
𝜋(𝐻) = 1 − .
𝜒(𝐻) − 1
Remark 1.5.2 (History). Erdős and Stone (1946) proved this result when 𝐻 is a complete
multipartite graph. Erdős and Simonovits (1966) observed that the general case follows as a
quick corollary. The proof given here is due to Erdős (1971).
Example 1.5.3. When 𝐻 = 𝐾𝑟+1 , 𝜒(𝐻) = 𝑟 + 1, and so Theorem 1.5.1 agrees with Turán’s
theorem.
Example 1.5.4. When 𝐻 is the Petersen graph (shown in what follows), which has chromatic
number 3, Theorem 1.5.1 tells us that ex(𝑛, 𝐻) = (1/4 + 𝑜(1))𝑛2 . The Turán density of the
Petersen graph is the same as that of a triangle, which may be somewhat surprising since the
Petersen graph seems more complicated than the triangle.
2
1
1 1
3 2
3 2
2 3
It suffices to establish the Erdős–Stone–Simonovits theorem for complete 𝑟-partite graphs

𝐻, since every 𝐻 with 𝜒(𝐻) = 𝑟 is a subgraph of some complete 𝑟-partite graph.
Theorem 1.5.5 (Erdős–Stone theorem)

Fix 𝑟 ≥ 2 and 𝑠 ≥ 1. Let 𝐻 = 𝐾𝑠,...,𝑠 be the complete 𝑟-partite graph with 𝑠 vertices in
each part. Then
2
1 𝑛
ex(𝑛, 𝐻) = 1 − + 𝑜(1) .
𝑟 −1 2
In other words, using the notation 𝐾𝑟 [𝑠] for 𝒔-blowup of 𝐾𝑟 , obtained by replacing each
vertex of 𝐾𝑟 by 𝑠 duplicates of itself (so that 𝐾𝑟 [𝑠] = 𝐻 in the preceding theorem statement),
the Erdős–Stone theorem says that
1
𝜋(𝐾𝑟 [𝑠]) = 𝜋(𝐾𝑟 ) = 1 − ,
𝑟 −1
In Section 1.3, we saw supersaturation (Theorem 1.3.4): when the edge density is signif-
icantly above the Turán density threshold 𝜋(𝐻), one finds not just a single copy of 𝐻 but
actually many copies. The Erdős–Stone theorem can be viewed in this light: above edge
density 𝜋(𝐻), we find a large blowup of 𝐻.
The proof uses the following hypergraph extension of the KST theorem, which we will
prove later in the section.
Recall the hypergraph Turán problem (Remark 1.3.3). Given an 𝑟-uniform hypergraph 𝐻
(also known as an 𝑟-graph), we write ex(𝑛, 𝐻) to be the maximum number of edges in an
𝐻-free 𝑟-graph.
The analogue of a complete bipartite graph for an 𝑟-graph is a complete 𝑟-partite 𝑟-graph
𝑲𝒔1 ,...,𝒔𝒓 . Its vertex set consists of disjoint vertex parts 𝑉1 , . . . , 𝑉𝑟 with |𝑉𝑖 | = 𝑠𝑖 for each 𝑖.
(𝒓 )
Every 𝑟-tuple in 𝑉1 × · · · × 𝑉𝑟 is an edge.
Theorem 1.5.6 (Hypergraph KST)

For every fixed positive integers 𝑟 ≥ 2 and 𝑠,
ex(𝑛, 𝐾𝑠,...,𝑠
(𝑟 )
) = 𝑜(𝑛𝑟 ).
Proof of the Erdős–Stone theorem (Theorem 1.5.5). We already saw the lower bound to
ex(𝑛, 𝐻) using a Turán graph. It remains to prove an upper bound.
Let 𝐺 be an 𝐻-free graph (where 𝐻 = 𝐾𝑠,...,𝑠 is the complete 𝑟-partite graph in the
theorem). Let 𝐺 (𝑟 ) be the 𝑟-graph with the same vertex set as 𝐺 and whose edges are the
𝑟-cliques in 𝐺. Note that 𝐺 (𝑟 ) is 𝐾𝑠,...,𝑠
(𝑟 )
-free, or else a copy of 𝐾𝑠,...,𝑠
(𝑟 )
in 𝐺 (𝑟 ) would be
supported by a copy of 𝐻 in 𝐺. Thus, by the hypergraph KST theorem (Theorem 1.5.6),
𝐺 (𝑟 ) has 𝑜(𝑛𝑟 ) edges. So 𝐺 has 𝑜(𝑛𝑟 ) copies of 𝐾𝑟 , and thus by the supersaturation theorem
1.5 Forbidding a General Subgraph: Erdős–Stone–Simonovits Theorem 29
quoted above, the edge density of 𝐺 is at most 𝜋(𝐾𝑟 ) + 𝑜(1), which equals 1 − 1/(𝑟 − 1) + 𝑜(1)
by Turán’s theorem. □
In Section 2.6, we will give another proof of the Erdős–Stone–Simonovits theorem using
the graph regularity method.
Hypergraph KST
To help keep notation simple, we first consider what happens for 3-uniform hypergraphs.
Theorem 1.5.7 (KST for 3-graphs)

For every 𝑠, there is some 𝐶 such that
2
ex(𝑛, 𝐾𝑠,𝑠,𝑠
(3)
) ≤ 𝐶𝑛3−1/𝑠 .
Recall that the KST theorem (Theorem 1.4.2) was proved by counting the number of
copies of 𝐾𝑠,1 in the graph in two different ways. For 3-graphs, we instead count the number
of copies of 𝐾𝑠,1,1
(3)
in two different ways, one of which uses the KST theorem for 𝐾𝑠,𝑠 -free
graphs.
Proof. Let 𝐺 be a 𝐾 𝑠,𝑠,𝑠 -free 3-graph with 𝑛 vertices and 𝑚 edges. Let 𝑋 denote the number
(3)
of copies of (3)
𝐾𝑠,1,1 in 𝐺. (When 𝑠 = 1, we count each copy three times.)
Upper bound on 𝑋. Given a set 𝑆 of 𝑠 vertices, consider the set 𝑇 of all unordered pairs
of distinct vertices that would form a 𝐾𝑠,1,1
(3)
with 𝑆 (i.e., every triple formed by combining
a pair in 𝑇 and a vertex of 𝑆 is an edge of 𝐺). Note that 𝑇 is the edge-set of a graph on the
same 𝑛 vertices. If 𝑇 contains a 𝐾𝑠,𝑠 , then together with 𝑆 we would have a 𝐾𝑠,𝑠,𝑠
(3)
. Thus 𝑇 is
2−1/𝑠
𝐾𝑠,𝑠 -free, and hence by Theorem 1.4.2, |𝑇 | = 𝑂 𝑠 (𝑛 ). Therefore,

𝑛 2−1/𝑠
𝑋 ≲𝑠 𝑛 ≲𝑠 𝑛𝑠+2−1/𝑠 .
𝑠
Lower bound on 𝑋. We write deg(𝑢, 𝑣) for the number of edges in 𝐺 containing both 𝑢
and 𝑣. Then, summing over all unordered pairs of distinct vertices 𝑢, 𝑣 in 𝐺, we have
∑︁ deg(𝑢, 𝑣)
𝑋= .
𝑢,𝑣
𝑠
As in the proof of Theorem 1.4.2, let

(
𝑥(𝑥 − 1) · · · (𝑥 − 𝑠 + 1)/𝑠! if 𝑥 ≥ 𝑠 − 1,
𝑓𝑠 (𝑥) =
0 𝑥 < 𝑠 − 1.

Then, 𝑓𝑠 is convex and 𝑓𝑠 (𝑥) = 𝑥𝑠 for all nonnegative integers 𝑥. Since the average of
deg(𝑢, 𝑣) is 3𝑚/ 𝑛2 ,
!
∑︁ 𝑛 3𝑚
𝑋= 𝑓𝑠 (deg(𝑢, 𝑣)) ≥ 𝑓𝑠 𝑛 .
𝑢,𝑣
2 2
Combining the upper and lower bounds, we have

!𝑠
𝑛 3𝑚
𝑛 ≲𝑠 𝑛𝑠+2−1/𝑠
2 2
and hence
2
𝑚 = 𝑂 𝑠 (𝑛3−1/𝑠 ). □
Exercise 1.5.8. Prove that ex(𝑛, 𝐾𝑟 ,𝑠,𝑡 ) = 𝑂 𝑟 ,𝑠,𝑡 (𝑛3−1/(𝑟 𝑠) ).

(3)
We can iterate further, using the same technique, to prove an analogous result for ev-
ery uniformity, thereby giving us the statement (Theorem 1.5.6) used in our proof of the
Erdős–Stone–Simonovits theorem earlier. Feel free to skip reading the next proof if you feel
comfortable with generalizing the above proof to 𝑟-graphs.
Theorem 1.5.9 (Hypergraph KST)

For every 𝑟 ≥ 2 and 𝑠 ≥ 1, there is some 𝐶 such that
ex(𝑛, 𝐾𝑠,...,𝑠
−𝑟+1
(𝑟 )
) ≤ 𝐶𝑛𝑟 −𝑠 ,
where 𝐾𝑠,...,𝑠
(𝑟 )
is the complete 𝑟-partite 𝑟-graph with 𝑠 vertices in each of the 𝑟 parts.
Proof. We prove by induction on 𝑟. The cases 𝑟 = 2 and 𝑟 = 3 were covered previously in

Theorem 1.4.2 and Theorem 1.5.7. Assume that 𝑟 ≥ 3 and that the theorem has already been
established for smaller values of 𝑟. (Actually we could have started at 𝑟 = 1 if we adjust the
definitions appropriately.)
Let 𝐺 be a 𝐾𝑠,...,𝑠
(𝑟 )
-free 𝑟-graph with 𝑛 vertices and 𝑚 edges. Let 𝑋 denote the number of
copies of 𝐾𝑠,1,...,1
(𝑟 )
in 𝐺 (when 𝑠 = 1, we count each copy 𝑟 times).
Upper bound on 𝑋. Given a set 𝑆 of 𝑠 vertices, consider the set 𝑇 of all unordered (𝑟 − 1)-
tuples of vertices that would form a 𝐾𝑠,1,...,1
(𝑟 )
with 𝑆 (where 𝑆 is in one part, and the 𝑟 − 1 new
vertices each in its own part). Note that 𝑇 is the edge-set of an (𝑟 − 1) graph on the same
𝑛 vertices. If 𝑇 contains a 𝐾𝑠,...,𝑠
(𝑟 −1)
, then together with 𝑆 we would have a 𝐾𝑠,...,𝑠
(𝑟 )
. Thus, 𝑇 is
(𝑟 −1)
-free, and by the induction hypothesis, |𝑇 | = 𝑂 𝑟 ,𝑠 (𝑛𝑟 −1−𝑠 ). Hence
−𝑟+2
𝐾𝑠,...,𝑠

𝑛 𝑟 −1−𝑠 −𝑟+2 −𝑟+2
𝑋 ≲𝑟 ,𝑠 𝑛 ≲𝑟 ,𝑠 𝑛𝑟+𝑠−1−𝑠 .
𝑠
Lower bound on 𝑋. Given a set 𝑈 of vertices, we write deg 𝑈 for the number of edges
containing all vertices in 𝑈. Then
∑︁ deg 𝑈
𝑋= .
𝑠
𝑈 ∈ ( 𝑉𝑟(𝐺)
−1 )
Let 𝑓𝑠 (𝑥) be defined as in the previous proof. Since the average of deg 𝑈 over all (𝑟 − 1)-
element subsets 𝑈 is 𝑟𝑚/ 𝑟 −1
𝑛
, we have
!
∑︁ 𝑛 𝑟𝑚
𝑋= 𝑓𝑠 (deg 𝑈) ≥ 𝑓𝑠 𝑛 .
𝑟 −1 −1
𝑈 ∈ ( 𝑟 −1 )
𝑉 (𝐺) 𝑟
1.6 Forbidding a Cycle 31
Combining the upper and lower bounds, we have

!
𝑛 𝑟𝑚
𝑛 ≲𝑟 ,𝑠 𝑛
𝑠+𝑟 −1−𝑠 −𝑟+2
𝑓𝑠
𝑟 −1 𝑟 −1
and hence
−𝑟+1
𝑚 = 𝑂 𝑟 ,𝑠 (𝑛𝑟 −𝑠 ). □
Exercise 1.5.10 (Forbidding a multipartite complete hypergraph with unbalanced parts).
Prove that for every sequence of positive integers 𝑠1 , . . . , 𝑠𝑟 , there exists 𝐶 so that
ex(𝑛, 𝐾𝑠(𝑟1 ,...,𝑠
)
𝑟
) ≤ 𝐶𝑛𝑟 −1/(𝑠1 ···𝑠𝑟 −1 ) .
Exercise 1.5.11 (Erdős–Stone for hypergraphs). Let 𝐻 be an 𝑟-graph. Show that 𝜋(𝐻 [𝑠]) =
𝜋(𝐻), where 𝐻 [𝑠], the 𝑠-blowup of 𝐻, is obtained by replacing every vertex of 𝐻 by 𝑠
duplicates of itself.
1.6 Forbidding a Cycle

In this section, we consider the problem of determining ex(𝑛, 𝐶ℓ ), the maximum number of
edges in an 𝑛-vertex graph without an ℓ-cycle.
Odd Cycles
First let us consider forbidding odd cycles. Let 𝑘 be a positive integer. Then 𝐶2𝑘+1 has
chromatic number 3, and so the Erdős–Stone–Simonovits theorem (Theorem 1.5.1) tells us
that
𝑛2
ex(𝑛, 𝐶2𝑘+1 ) = (1 + 𝑜(1)) .
4
In fact, an even stronger statement is true. If 𝑛 is large enough (as a function of 𝑘), then the
complete bipartite graph 𝐾 ⌊𝑛/2⌋,⌈𝑛/2⌉ is always the extremal graph, just like in the triangle
case.
Theorem 1.6.1 (Exact Turán number of an odd cycle)

Let 𝑘 be a positive integer. Then for all sufficiently large integer 𝑛 (i.e., 𝑛 ≥ 𝑛0 (𝑘) for
some 𝑛0 (𝑘)), one has
2
𝑛
ex(𝑛, 𝐶2𝑘+1 ) = .
4
We will not prove this theorem. See Füredi and Gunderson (2015) for a more recent proof.
More generally, Simonovits (1974) developed a stability method for exactly determining
the Turán number of nonbipartite color-edge-critical graphs. Here we say that a graph if
color-edge-critical if the removal of any edge strictly reduces the chromatic number.
Theorem 1.6.2 (Exact Turán number of a color-edge-critical graph)

Let 𝐹 be a color-edge-critical graph with chromatic number 𝑟 + 1 ≥ 3. Then for all
sufficiently large 𝑛 (i.e., 𝑛 ≥ 𝑛0 (𝐹) for some 𝑛0 (𝐹)), the Turán graph 𝑇𝑛,𝑟 uniquely
maximizes the number of edges among all 𝑛-vertex 𝐹-free graphs.
Forbidding Even Cycles

Let us now turn to forbidding even cycles. Since 𝐶2𝑘 is bipartite, we know from the KST
theorem that ex(𝑛, 𝐶2𝑘 ) = 𝑜(𝑛2 ). The following upper bound was determined by Bondy and
Simonovits (1974).
Theorem 1.6.3 (Even cycles)
For every integer 𝑘 ≥ 2, there exists a constant 𝐶 so that
ex(𝑛, 𝐶2𝑘 ) ≤ 𝐶𝑛1+1/𝑘 .
Remark 1.6.4 (Tightness). We will see in Section 1.10 a matching lower bound construction
(up to constant factors) for 𝑘 = 2, 3, 5. For all other values of 𝑘, it is an open question whether
a matching lower bound construction exists.
Instead of proving the preceding theorem, we will prove a weaker result, stated in what
follows. This weaker result has a short and neat proof, which hopefully gives some intuition
as to why the above theorem should be true.
Theorem 1.6.5 (Short even cycles)

For any integer 𝑘 ≥ 2, there exists a constant 𝐶 so that every graph 𝐺 with 𝑛 vertices and
at least 𝐶𝑛1+1/𝑘 edges contains an even cycle of length at most 2𝑘.
In other words, Theorem 1.6.5 says that

ex(𝑛, {𝐶4 , 𝐶6 , . . . , 𝐶2𝑘 }) = 𝑂 𝑘 (𝑛1+1/𝑘 ).
Here, given a set F of graphs, ex(𝑛, F ) denotes the maximum number of edges in an 𝑛-vertex
graph that does not contain any graph in F as a subgraph.
To prove this theorem, we first clean up the graph by removing some edges and vertices
to get a bipartite subgraph with large minimum degree.
Lemma 1.6.6 (Large bipartite subgraph)

Every 𝐺 has a bipartite subgraph with at least 𝑒(𝐺)/2 edges.
Proof. Color every vertex with red or blue independently and uniformly at random. Then
the expected number of nonmonochromatic edges is 𝑒(𝐺)/2. Hence there exists a coloring
that has at least 𝑒(𝐺)/2 nonmonochromatic edges, and these edges form the desired bipartite
subgraph. □
Lemma 1.6.7 (Large average degree implies subgraph with large minimum degree)
Let 𝑡 > 0. Every graph with average degree 2𝑡 has a subgraph with minimum degree
greater than 𝑡.
1.7 Forbidding a Sparse Bipartite Graph: Dependent Random Choice 33
Proof. Let 𝐺 be a graph with average degree 2𝑡. Removing a vertex of degree at most 𝑡
cannot decrease the average degree, since the total degree goes down by at most 2𝑡 and so
the post-deletion graph has average degree of at least (2𝑒(𝐺) − 2𝑡)/(𝑣(𝐺) − 1), which is
at least 2𝑒(𝐺)/𝑣(𝐺) since 2𝑒(𝐺)/𝑣(𝐺) ≥ 2𝑡. Let us repeatedly delete vertices of degree at
most 𝑡 in the remaining graph until every vertex has degree more than 𝑡. This algorithm must
terminate with a nonempty graph since we cannot ever drop below 2𝑡 vertices in this process
(as such a graph would have average degree less than 2𝑡). □
Proof of Theorem 1.6.5. The idea is to use a breath-first search. Suppose 𝐺 contains no
even cycles of length at most 2𝑘. Applying Lemma 1.6.6 followed by Lemma 1.6.7, we find
a bipartite subgraph 𝐺 ′ of 𝐺 with minimum degree > 𝑡 B 𝑒(𝐺)/(2𝑣(𝐺)). Let 𝑢 be an
arbitrary vertex of 𝐺 ′ . For each 𝑖 = 0, 1, . . . , 𝑘, let 𝐴𝑖 denote the set of vertices at distance
exactly 𝑖 from 𝑢.
···
𝑢 ···
𝐴0
···
𝐴1
𝐴2 𝐴𝑘
For each 𝑖 = 1, . . . , 𝑘 − 1, every vertex of 𝐴𝑖 has

• no neighbors inside 𝐴𝑖 (or else 𝐺 ′ would not be bipartite),
• exactly one neighbor in 𝐴𝑖−1 (else we can backtrace through two neighbors, which must
converge at some point to form an even cycle of length at most 2𝑘),
• and thus > 𝑡 − 1 neighbors in 𝐴𝑖+1 (by the minimum degree assumption on 𝐺 ′ ).
Therefore, each layer 𝐴𝑖 expands to the next by a factor of at least 𝑡 − 1. Hence
𝑘
𝑒(𝐺)
𝑣(𝐺) ≥ | 𝐴 𝑘 | ≥ (𝑡 − 1) 𝑘 ≥ −1
2𝑣(𝐺)
and thus
𝑒(𝐺) ≤ 2𝑣(𝐺) 1+1/𝑘 + 2𝑣(𝐺). □
Exercise 1.6.8 (Extremal number of trees). Let 𝑇 be a tree with 𝑘 edges. Show that
ex(𝑛, 𝑇) ≤ 𝑘𝑛.
1.7 Forbidding a Sparse Bipartite Graph: Dependent Random Choice

Every bipartite graph 𝐻 is contained in some 𝐾𝑠,𝑡 , and thus by the KST theorem (Theo-
rem 1.4.2), ex(𝑛, 𝐻) ≤ ex(𝑛, 𝐾𝑠,𝑡 ) = 𝑂 𝑠,𝑡 (𝑛2−1/𝑠 ). The main result of this section gives a
significant improvement when the maximum degree of 𝐻 is small. The proof introduces an
important probabilistic technique known as dependent random choice.
Theorem 1.7.1 (Bounded degree bipartite graph: Turán number upper bound)
Let 𝐻 be a bipartite graph with vertex bipartition 𝐴 ∪ 𝐵 such that every vertex in 𝐴 has
degree at most 𝑟. Then there exists a constant 𝐶 = 𝐶𝐻 such that for all 𝑛,
ex(𝑛, 𝐻) ≤ 𝐶𝑛2−1/𝑟 .
Remark 1.7.2 (History). The result was first proved by Füredi (1991). The proof given here
is due to Alon, Krivelevich, and Sudakov (2003a). For more applications of the dependent
random choice technique see the survey by Fox and Sudakov (2011).
Remark 1.7.3 (Tightness). The exponent 2 − 1/𝑟 is best possible as a function of 𝑟. Indeed,
we will see in the following section that for every 𝑟 there exists some 𝑠 so that ex(𝑛, 𝐾𝑟 ,𝑠 ) ≥
𝑐𝑛2−1/𝑟 for some 𝑐 = 𝑐(𝑟, 𝑠) > 0.
On the other hand, for specific graphs 𝐺, Theorem 1.7.1 may not be tight. For example,
ex(𝑛, 𝐶6 ) = Θ(𝑛4/3 ), whereas Theorem 1.7.1 only tells us that ex(𝑛, 𝐶6 ) = 𝑂 (𝑛3/2 ).
Given a graph 𝐺 with many edges, we wish to find a large subset 𝑈 of vertices such
that every 𝑟-vertex subset of 𝑈 has many common neighbors in 𝐺. (Even the case 𝑟 = 2 is
interesting.) Once such a 𝑈 is found, we can then embed the 𝐵-vertices of 𝐻 into 𝑈. It will
then be easy to embed the vertices of 𝐴. The tricky part is to find such a 𝑈.
Remark 1.7.4 (Intuition). We want to host a party so that each pair of partygoers has many
common friends. (Here 𝐺 is the friendship graph.) Whom should we invite? Inviting people
uniformly at random is not a good idea. (Why?) Perhaps we can pick some random individual
(Alice) to host a party inviting all her friends. Alice’s friends are expected to share some
common friends – at least they all know Alice.
We can take a step further, and pick a few people at random (Alice, Bob, Carol, David)
and have them host a party and invite all their common friends. This will likely be an even
more sociable crowd. At least all the party goers will know all the hosts, and likely even
more. As long as the social network is not too sparse, there should be lots of invitees.
Some invitees (e.g., Zack) might feel a bit out of place at the party – maybe they don’t
have many common friends with other partygoers. (They all know the hosts but maybe
Zack doesn’t know many others.) To prevent such awkwardness, the hosts will cancel Zack’s
invitation. There shouldn’t be too many people like Zack. The party must go on.
Here is the technical statement that we will prove. While there are many parameters, the
specific details are less important compared to the proof technique. This is quite a tricky
proof.
Theorem 1.7.5 (Dependent random choice)

Let 𝑛, 𝑟, 𝑚, 𝑡 be positive integers and 𝛼 > 0. Then every graph 𝐺 with 𝑛 vertices and at
least 𝛼𝑛2 /2 edges contains a vertex subset 𝑈 with

𝑡 𝑛 𝑚 𝑡
|𝑈| ≥ 𝑛𝛼 −
𝑟 𝑛
such that every 𝑟-element subset 𝑆 of 𝑈 has more than 𝑚 common neighbors in 𝐺.
1.7 Forbidding a Sparse Bipartite Graph: Dependent Random Choice 35
Remark 1.7.6 (Parameters). In the theorem statement, 𝑡 is an auxiliary parameter that does
not appear in the conclusion. While one can optimize for 𝑡, it is instructive and convenient to
leave it as is. The theorem is generally applied to graphs with at least 𝑛2−𝑐 edges, for some
small 𝑐 > 0, and we can play with the parameters to get |𝑈| and 𝑚 both large as desired.
Proof. We say that an 𝑟-element subset of 𝑉 (𝐺) is “bad” if it has at most 𝑚 common
neighbors in 𝐺.
Let 𝑢 1 , . . . , 𝑢 𝑡 be vertices chosen uniformly and independently at random from 𝑉 (𝐺).
(These vertices are chosen “with replacement,” i.e., they can repeat.) Let 𝐴 be their common
neighborhood. (Keep in mind that 𝑢 1 , . . . , 𝑢 𝑡 , 𝐴 are random. It may be a bit confusing in this
proof to see what is random and what is not.)
𝑢1 ... 𝑢𝑡
Each fixed vertex 𝑣 ∈ 𝑉 (𝐺) has probability (deg(𝑣)/𝑛) 𝑡 of being adjacent to all of 𝑢 1 , . . . , 𝑢 𝑡 ,
and so, by linearity of expectations and convexity,
!𝑡
∑︁ ∑︁ deg(𝑣) 𝑡 1 ∑︁ deg(𝑣)
E | 𝐴| = P(𝑣 ∈ 𝐴) = ≥𝑛 ≥ 𝑛𝛼𝑡 .
𝑣 ∈𝑉 (𝐺) 𝑣 ∈𝑉 (𝐺)
𝑛 𝑛 𝑣 ∈𝑉
𝑛
For any fixed 𝑅 ⊆ 𝑉 (𝐺),

𝑡
# common neighbors of 𝑅
P(𝑅 ⊆ 𝐴) = P(𝑅 is complete to 𝑢 1 , . . . , 𝑢 𝑡 ) = .
𝑛
If 𝑅 is a bad 𝑟-vertex subset, then it has at most 𝑚 common neighbors, and so
𝑚 𝑡
P(𝑅 ⊆ 𝐴) ≤ .
𝑛

Therefore, summing over all 𝑛𝑟 possible 𝑟-vertex subsets 𝑅 ⊆ 𝑉 (𝐺), by linearity of expec-
tation,

𝑛 𝑚 𝑡
E[the number of bad 𝑟-vertex subsets of 𝐴] ≤ .
𝑟 𝑛
Let 𝑈 be obtained from 𝐴 by deleting an element from each bad 𝑟-vertex subset. So, 𝑈 has
no bad 𝑟-vertex subsets. Also,
E |𝑈| ≥ E | 𝐴| − E[the number of bad 𝑟-vertex subsets of 𝐴]

𝑡 𝑛 𝑚 𝑡
≥ 𝑛𝛼 − .
𝑟 𝑛
Thus, there exists some 𝑈 with at least this size, with the property that all its 𝑟-vertex subsets
have more than 𝑚 common neighbors. □
Now we are ready to show Theorem 1.7.1, which we recall says that, for a bipartite graph
𝐻 with vertex bipartition 𝐴 ∪ 𝐵 such that every vertex in 𝐴 has degree at most 𝑟, one has
ex(𝑛, 𝐻) = 𝑂 𝐻 (𝑛2−1/𝑟 ).
Proof of Theorem 1.7.1. Let 𝐺 be a graph with 𝑛 vertices and at least 𝐶𝑛2−1/𝑟 edges. By
choosing 𝐶 large enough (depending only on | 𝐴| + |𝐵|), we have
𝑟 𝑛 | 𝐴| + |𝐵| 𝑟
𝑛 2𝐶𝑛 −1/𝑟
− ≥ |𝐵| .
𝑟 𝑛
We want to show that 𝐺 contains 𝐻 as a subgraph. By dependent random choice (Theo-
rem 1.7.5 applied with 𝑡 = 𝑟), we can embed the 𝐵-vertices of 𝐻 into 𝐺 so that every 𝑟-vertex
subset of 𝐵 (now viewed as a subset of 𝑉 (𝐺)) has > | 𝐴| + |𝐵| common neighbors.
𝐴 𝐵
𝑏1 𝑁 (𝑏1 ) ∩ 𝑁 (𝑏2 ) ∩ 𝑁 (𝑏3 )

𝑣
𝑏2
𝑏3
𝑏4 𝑏1 𝑏2 𝑏3 𝑏4
𝐻 𝐺
Next, we embed the vertices of 𝐴 one at a time. Suppose we need to embed 𝑣 ∈ 𝐴 (some
previous vertices of 𝐴 may have already been embedded at this point). Note that 𝑣 has ≤ 𝑟
neighbors in 𝐵, and these ≤ 𝑟 vertices in 𝐵 have > | 𝐴| + |𝐵| common neighbors in 𝐺. While
some of these common neighbors may have already been used up in earlier steps to embed
vertices of 𝐻, there are enough of them that they cannot all be used up, and thus we can
embed 𝑣 to some remaining common neighbor. This process ends with an embedding of 𝐻
into 𝐺. □
Exercise 1.7.7. Let 𝐻 be a bipartite graph with vertex bipartition 𝐴 ∪ 𝐵, such that 𝑟
vertices in 𝐴 are complete to 𝐵, and all remaining vertices in 𝐴 have degree at most 𝑟.
Prove that there is some constant 𝐶 = 𝐶𝐻 such that ex(𝑛, 𝐻) ≤ 𝐶𝑛2−1/𝑟 for all 𝑛.
Exercise 1.7.8. Let 𝜀 > 0. Show that, for sufficiently large 𝑛, every 𝐾4 -free graph with 𝑛
vertices and at least 𝜀𝑛2 edges contains an independent set of size at least 𝑛1− 𝜀 .
1.8 Lower Bound Constructions: Overview 37
Exercise 1.7.9 (Extremal numbers of degenerate graphs).

(a*) Prove that there is some absolute constant 𝑐 > 0 so that for every positive integer 𝑟,
every 𝑛-vertex graph with at least 𝑛2−𝑐/𝑟 edges contains disjoint nonempty vertex
subsets 𝐴 and 𝐵 such that every subset of at most 𝑟 vertices in 𝐴 has at least 𝑛𝑐
common neighbors in 𝐵 and every subset of at most 𝑟 vertices in 𝐵 has at least 𝑛𝑐
neighbors in 𝐴.
forth to the two vertex parts.
Hint: Apply the technique from the dependent random choice proof repeatedly back and
(b) We say that a graph 𝐻 is 𝒓-degenerate if its vertices can be ordered so that every
vertex has at most 𝑟 neighbors that appear before it in the ordering. Show that
for every 𝑟-degenerate bipartite graph 𝐻 there is some constant 𝐶 > 0 so that
ex(𝑛, 𝐻) ≤ 𝐶𝑛2−𝑐/𝑟 , where 𝑐 is the same absolute constant from part (a). (Here 𝑐
should not depend on 𝐻 or 𝑟.)
1.8 Lower Bound Constructions: Overview

We proved various upper bounds on ex(𝑛, 𝐻) in earlier sections. When 𝐻 is nonbipartite,
the Turán graph construction (Construction 1.2.2) shows that the upper bound in the Erdős–
Stone–Simonovits theorem (Theorem 1.5.1) is tight up to lower-order terms. However, when
𝐻 is bipartite, so that ex(𝑛, 𝐻) = 𝑜(𝑛2 ), we have not seen any nontrivial lower bound
constructions. In the remainder of this chapter, we will see some methods for constructing
𝐻-free graphs for bipartite 𝐻. In some cases, these constructions will have enough edges to
match the upper bounds on ex(𝑛, 𝐻) from earlier sections. However, for most bipartite graphs
𝐻, there is a gap in known upper and lower bounds on ex(𝑛, 𝐻). It is a central problem in
extremal graph theory to close this gap.
We will see three methods for constructing 𝐻-free graphs.
Randomized Constructions
The idea is to take a random graph at a density that gives a small number of copies of 𝐻,
and then destroy these copies of 𝐻 by removing some edges from the random graph. The
resulting graph is then 𝐻-free. This method is easy to implement and applies quite generally
to all 𝐻. For example, it will be shown that
𝑣 (𝐻) −2
ex(𝑛, 𝐻) = Ω𝐻 𝑛2− 𝑒 (𝐻) −1 .
However, bounds arising from this method are usually not tight.
Algebraic Constructions
The idea is to use algebraic geometry over a finite field to construct a graph. Its vertices
correspond to geometric objects such as points or lines. Its edges correspond to incidences
or other algebraic relations. These constructions sometimes give tight bounds. They work
for a small number of graphs 𝐻, and usually require a different ad hoc idea for each 𝐻. They
work rarely, but when they do, they can appear quite mysterious, or even magical. Many
important tight lower bounds on bipartite extremal numbers arise this way. In particular it
will be shown that

ex(𝑛, 𝐾𝑠,𝑡 ) = Ω𝑠,𝑡 𝑛2−1/𝑠 whenever 𝑡 ≥ (𝑠 − 1)! + 1,
thereby matching the KST theorem (Theorem 1.4.2) for such 𝑠, 𝑡. Also, it will be shown that

ex(𝑛, 𝐶2𝑘 ) = Ω𝑘 𝑛1+1/𝑘 whenever 𝑘 ∈ {2, 3, 5},
thereby matching Theorem 1.6.3 for these values of 𝑘.
Randomized Algebraic Constructions

In algebraic constructions, usually we specify the edges using some specific well-chosen
polynomials. A powerful recent idea is to choose the edge-defining polynomials at random.
1.9 Randomized Constructions

We use the probabilistic method to construct an 𝐻-free graph. The Erdős–Rényi random
graph G(𝑛, 𝑝) is the random graph on 𝑛 vertices where every pair of vertices forms an edge
independently with probability 𝑝. We first take a G(𝑛, 𝑝) with an appropriately chosen 𝑝.
The number of copies of 𝐻 in G(𝑛, 𝑝) is expected to be small, and we can destroy all such
copies of 𝐻 from the random graph by removing some edges. The remaining graph will then
be 𝐻-free.
The method of starting with a simple random object and then modifying it is sometimes
called alteration method or the deletion method.
Theorem 1.9.1 (Randomized lower bound)
Let 𝐻 be a graph with at least two edges. Then there exists a constant 𝑐 = 𝑐 𝐻 > 0, so that
𝑣 (𝐻) −2
for all 𝑛 ≥ 2, there exists an 𝐻-free graph on 𝑛 vertices with at least 𝑐𝑛2− 𝑒 (𝐻) −1 edges. In
other words,
𝑣 (𝐻) −2
ex(𝑛, 𝐻) ≥ 𝑐𝑛2− 𝑒 (𝐻) −1 .
Proof. Let 𝐺 be an instance of the Erdős–Rényi random graph G(𝑛, 𝑝), with
1 − 𝑒𝑣 (𝐻)
(𝐻) −2
𝑝= 𝑛 −1
4

(chosen with hindsight). We have E 𝑒(𝐺) = 𝑝 𝑛2 . Let 𝑋 denote the number of copies of 𝐻
in 𝐺. Then, our choice of 𝑝 ensures that

𝑒 (𝐻 ) 𝑣 (𝐻 ) 𝑝 𝑛 1
E𝑋 ≤ 𝑝 𝑛 ≤ = E 𝑒(𝐺).
2 2 2
Thus
𝑝 𝑛 𝑣 (𝐻) −2
E[𝑒(𝐺) − 𝑋] ≥ ≳ 𝑛2− 𝑒 (𝐻) −1 .
2 2
Take a graph 𝐺 such that 𝑒(𝐺) − 𝑋 is at least its expectation. Remove one edge from each
𝑣 (𝐻) −2
copy of 𝐻 in 𝐺, and we get an 𝐻-free graph with at least 𝑒(𝐺) − 𝑋 ≳ 𝑛2− 𝑒 (𝐻) −1 edges. □
1.9 Randomized Constructions 39
For some graphs 𝐻, we can bootstrap Theorem 1.9.1 to give an even better lower bound.
For example, if
𝐻= ,
then 𝑣(𝐻) = 10 and 𝑒(𝐻) = 20, so applying Theorem 1.9.1 directly gives
ex(𝑛, 𝐻) ≳ 𝑛2−8/19 .
On the other hand, any 𝐾4,4 -free graph is automatically 𝐻-free. Applying Theorem 1.9.1 to
𝐾4,4 (8-vertex 16-edge) actually gives a better lower bound (2 − 6/15 > 2 − 8/19):
ex(𝑛, 𝐻) ≥ ex(𝑛, 𝐾4,4 ) ≳ 𝑛2−6/15 .
In general, given 𝐻, we should apply Theorem 1.9.1 to the subgraph of 𝐻 with the
maximum (𝑒(𝐻) − 1)/(𝑣(𝐻) − 2) ratio. This gives the following corollary, which sometimes
gives a better lower bound than directly applying Theorem 1.9.1.
Definition 1.9.2 (2-density)

The 2-density of a graph 𝐻 is defined by
𝑒(𝐻 ′ ) − 1
𝒎 2 (𝑯) B max .
′
𝐻 ⊆𝐻 𝑣(𝐻 ′ ) − 2
𝑒 (𝐻 ′ ) ≥2
Corollary 1.9.3 (Randomized lower bound)

For any graph 𝐻 with at least two edges, there exists constant 𝑐 = 𝑐 𝐻 > 0 such that
ex(𝑛, 𝐻) ≥ 𝑐𝑛2−1/𝑚2 (𝐻 ) .
𝑒 (𝐻 ′ ) −1
Proof. Let 𝐻 ′ be the subgraph of 𝐻 with 𝑚 2 (𝐻) = 𝑣 (𝐻 ′ ) −2
.Then ex(𝑛, 𝐻) ≥ ex(𝑛, 𝐻 ′ ), and
2−1/𝑚2 (𝐻 )
we can apply Theorem 1.9.1 to get ex(𝑛, 𝐻) ≥ 𝑐𝑛 . □
Example 1.9.4. Theorem 1.9.1 combined with the upper bound from the KST theorem
(Theorem 1.4.2) gives that for every fixed 2 ≤ 𝑠 ≤ 𝑡,
1
𝑛2− 𝑠𝑡 −1 ≲ ex(𝑛, 𝐾𝑠,𝑡 ) ≲ 𝑛2− 𝑠 .
𝑠+𝑡 −2
When 𝑡 is large compared to 𝑠, the exponents in the preceding two bounds are close to each
other (but never equal). When 𝑡 = 𝑠, the preceding bounds specialize to
2 1
𝑛2− 𝑠+1 ≲ ex(𝑛, 𝐾𝑠,𝑠 ) ≲ 𝑛2− 𝑠 .
In particular, for 𝑠 = 2,
𝑛4/3 ≲ ex(𝑛, 𝐾2,2 ) ≲ 𝑛3/2 .
It turns out that the upper bound is tight. We will show this in the next section using an
algebraic construction.
Exercise 1.9.5. Show that if 𝐻 is a bipartite graph containing a cycle of length 2𝑘, then
ex(𝑛, 𝐻) ≳𝐻 𝑛1+1/(2𝑘−1) .
1 2
Exercise 1.9.6. Find a graph 𝐻 with 𝜒(𝐻) = 3 and ex(𝑛, 𝐻) > 4
𝑛 + 𝑛1.99 for all
sufficiently large 𝑛.
1.10 Algebraic Constructions

In this section, we use algebraic methods to construct 𝐾𝑠,𝑡 -free graphs for certain values of
(𝑠, 𝑡), as well as 𝐶2𝑘 -free graphs for certain values of 𝑘. In both cases, the constructions are
optimal in that they match the upper bounds up to a constant factor.
𝐾2,2 -free
We begin by constructing 𝐾2,2 -free graphs with the number of edges matching the KST
theorem. The construction is due to Erdős, Rényi, and Sós (1966) and Brown (1966) inde-
pendently.
Theorem 1.10.1 (Construction of 𝐾2,2 -free graphs)

1
ex(𝑛, 𝐾2,2 ) ≥ − 𝑜(1) 𝑛3/2 .
2
Combining with the KST theorem, we obtain the corollary.
Corollary 1.10.2 (Turán number of 𝐾2,2 )

1
ex(𝑛, 𝐾2,2 ) = − 𝑜(1) 𝑛3/2 .
2
Before giving the proof of Theorem 1.10.1, let us first sketch the geometric intuition.
Given a set of points P and a set of lines L, the point-line incidence graph is the bipartite
graph with two vertex parts P and L, where 𝑝 ∈ P and ℓ ∈ L are adjacent if 𝑝 ∈ ℓ.
P 𝑝∈ℓ L
𝑝
ℓ
A point-line incidence graph is 𝐶4 -free. Indeed, a 𝐶4 would correspond to two lines both
passing through two distinct points, which is impossible.
We want to construct a set of points and a set of lines so that there are many incidences.
To do this, we take all points and all lines in a finite field plane F2𝑝 . There are 𝑝 2 points
1.10 Algebraic Constructions 41
and 𝑝 2 + 𝑝 lines. Since every line contains 𝑝 points, the graph has around 𝑝 3 edges, and
so ex(2𝑝 2 + 𝑝, 𝐾2,2 ) ≥ 𝑝 3 . By rounding down an integer 𝑛 to the closest number of the
form 2𝑝 2 + 𝑝 for a prime 𝑝, we already see that ex(𝑛, 𝐾2,2 ) ≳ 𝑛3/2 for all 𝑛. Here we use a
theorem from number theory regarding large gaps in primes, which we quote in what follows
without proof. (This strategy does not work if we instead take points and lines in R2 ; see the
Szemerédi–Trotter theorem in Section 8.2).
Theorem 1.10.3 (Large gaps between primes)

The largest prime below 𝑁 has size 𝑁 − 𝑜(𝑁).
Remark 1.10.4 (Large gaps between primes). The preceding result already follows from
the prime number theorem, which says that the number of primes up to 𝑁 is (1+𝑜(1))𝑁/log 𝑁.
The best quantitative result, due to Baker, Harman, and Pintz (2001), says that there exists a
prime in [𝑁 − 𝑁 0.525 , 𝑁] for all sufficiently large 𝑁. Cramer’s conjecture, which is wide open
and based on a random model of the primes, speculates that the 𝑜(𝑁) in Theorem 1.10.3 may
be replaced by 𝑂 ((log 𝑁) 2 ). An easier claim is Bertrand’s postulate, which says that there is a
prime between 𝑁 and 2𝑁 for every 𝑁, and this already suffices for proving ex(𝑛, 𝐾2,2 ) ≳ 𝑛3/2 .
To get a better constant in the preceding construction, we optimize somewhat by using the
same vertices to represent both points and lines. This pairing of points and lines is known as
polarity in projective geometry, and this construction is known as the polarity graph. (This
usually refers to the projective plane version of the construction.)
Proof of Theorem 1.10.1. Let 𝑝 denote the largest prime such that 𝑝 2 − 1 ≤ 𝑛. Then 𝑝 =
√
(1 − 𝑜(1)) 𝑛 by Theorem 1.10.3. Let 𝐺 be a graph with vertex set 𝑉 (𝐺) = F2𝑝 \ {(0, 0)} and
an edge between (𝑥, 𝑦) and (𝑎, 𝑏) if and only if 𝑎𝑥 + 𝑏𝑦 = 1 in F 𝑝 .
For any two distinct vertices (𝑎, 𝑏) and (𝑎 ′ , 𝑏 ′ ) in 𝑉 (𝐺), they have at most one common
neighbor since there is at most one solution to the system 𝑎𝑥 + 𝑏𝑦 = 1 and 𝑎 ′ 𝑥 + 𝑏 ′ 𝑦 = 1.
Therefore, 𝐺 is 𝐾2,2 -free. (This is where we use the fact that two lines intersect in at most
one point.)
For every (𝑎, 𝑏) ∈ 𝑉 (𝐺), there are exactly 𝑝 vertices (𝑥, 𝑦) satisfying 𝑎𝑥 + 𝑏𝑦 = 1.
However, one of those vertices could be (𝑎, 𝑏) itself. So every vertex in 𝐺 has degree 𝑝 or
𝑝 − 1. Hence 𝐺 has at least ( 𝑝 2 − 1) ( 𝑝 − 1)/2 = (1/2 − 𝑜(1))𝑛3/2 edges. □
𝐾3,3 -free
Next, we construct 𝐾3,3 -free graphs with the number of edges matching the KST theorem.
This construction is due to Brown (1966).
Theorem 1.10.5 (Construction of 𝐾3,3 -free graphs)

For every 𝑛,

1
ex(𝑛, 𝐾3,3 ) ≥ − 𝑜(1) 𝑛5/3 .
2
Consider the incidences between points in R3 and unit spheres. This graph is 𝐾3,3 -free
since no three unit spheres can share three distinct common points. Again, one needs to do
this over a finite field to attain the desired bounds, but it is easier to visualize the setup in
Euclidean space, where it is clearly true.
Proof sketch. Let 𝑝 be the largest prime less than 𝑛1/3 . Fix a nonzero element 𝑑 ∈ F 𝑝 , which
we take to be a quadratic residue if 𝑝 ≡ 3 (mod 4) and a quadratic nonresidue if 𝑝 . 3
(mod 4). Construct a graph 𝐺 with vertex set 𝑉 (𝐺) = F3𝑝 , and an edge between (𝑥, 𝑦, 𝑧) and
(𝑎, 𝑏, 𝑐) ∈ 𝑉 (𝐺) if and only if
(𝑎 − 𝑥) 2 + (𝑏 − 𝑦) 2 + (𝑐 − 𝑧) 2 = 𝑑.
It turns out that each vertex has (1 − 𝑜(1)) 𝑝 2 neighbors. (The intuition here is that, for a
fixed (𝑎, 𝑏, 𝑐), if we choose 𝑥, 𝑦, 𝑧 ∈ F 𝑝 independently and uniformly at random, then the
resulting sum (𝑎 − 𝑥) 2 + (𝑏 − 𝑦) 2 + (𝑐 − 𝑧) 2 is roughly uniformly distributed, and hence
equals to 𝑑 with probability close to 1/𝑝.) It remains to show that the graph is 𝐾3,3 -free.
To see this, think about how one might prove this claim in R3 via algebraic manipulations.
We compute the radical planes between pairs of spheres as well as the intersections of these
radical planes (i.e., the radical axis). The claim boils down to the fact that no sphere has three
collinear points, which is true due to the quadratic (non)residue hypothesis on 𝑑. The details
are omitted.
Thus 𝐺 is a 𝐾3,3 -free graph on 𝑝 3 ≤ 𝑛 vertices and with at least (1/2 − 𝑜(1)) 𝑝 5 =
(1/2 − 𝑜(1))𝑛5/3 edges. □
It is unknown if the preceding ideas can be extended to construct 𝐾4,4 -free graphs with
Ω(𝑛7/4 ) edges. It is a major open problem to determine the asymptotics of ex(𝑛, 𝐾4,4 ).
Conjecture 1.10.6 (KST theorem is tight)

For every fixed 𝑠 ≥ 4, one has
ex(𝑛, 𝐾𝑠,𝑠 ) = Θ𝑠 (𝑛2−1/𝑠 ).
𝐾𝑠,𝑡 -free
Now we present a substantial generalization of the above constructions, due to Kollár, Rónyai,
and Szabó (1996) and Alon, Rónyai, and Szabó (1999). It gives a matching lower bound (up
to a constant factor) to the KST theorem for 𝐾𝑠,𝑡 whenever 𝑡 is sufficiently large compared to
𝑠.
Theorem 1.10.7 (Tightness of KST bound when 𝑡 > (𝑠 − 1)!)

Fix a positive integer 𝑠 ≥ 2. Then

1
ex(𝑛, 𝐾𝑠, (𝑠−1)!+1 ) ≥ − 𝑜(1) 𝑛2−1/𝑠 .
2
Corollary 1.10.8 (Tightness of KST bound when 𝑡 > (𝑠 − 1)!)

If 𝑡 > (𝑠 − 1)!, then
ex(𝑛, 𝐾𝑠,𝑡 ) = Θ𝑠,𝑡 (𝑛2−1/𝑠 ).
We first prove a slightly weaker version of Theorem 1.10.7, namely that

1
ex(𝑛, 𝐾𝑠,𝑠!+1 ) ≥ − 𝑜(1) 𝑛2−1/𝑠 .
2
(Kollár, Rónyai, and Szabó 1996). Afterwards, we will modify the construction to prove
Theorem 1.10.7.
Let 𝑝 be a prime. Recall that the norm map 𝑁 : F 𝑝 𝑠 → F 𝑝 is defined by
2 𝑠−1 𝑝 𝑠 −1
𝑁 (𝑥) B 𝑥 · 𝑥 𝑝 · 𝑥 𝑝 · · · 𝑥 𝑝 =𝑥 𝑝−1 .
Note that 𝑁 (𝑥) ∈ F 𝑝 for all 𝑥 ∈ F 𝑝 𝑠 since 𝑁 (𝑥) 𝑝 = 𝑁 (𝑥) and F 𝑝 is the set of elements in
F 𝑝 𝑠 invariant under the automorphism 𝑥 ↦→ 𝑥 𝑝 . Furthermore, since F×𝑝 𝑠 is a cyclic group of
order 𝑝 𝑠 − 1, we know that
𝑝𝑠 − 1
{𝑥 ∈ F 𝑝 𝑠 : 𝑁 (𝑥) = 1} = . (1.2)
𝑝−1
Construction 1.10.9 (Norm graph)

NormGraph 𝒑,𝒔 is defined to be the graph with vertex set F 𝑝 𝑠 and an edge between distinct
𝑎, 𝑏 ∈ F 𝑝 𝑠 if 𝑁 (𝑎 + 𝑏) = 1.
By (1.2), every vertex in NormGraph 𝑝,𝑠 has degree at least

𝑝𝑠 − 1
− 1 ≥ 𝑝 𝑠−1 .
𝑝−1
(We had to subtract 1 in case 𝑁 (𝑥 + 𝑥) = 1.) And thus the number of edges is at least 𝑝 2𝑠−1 /2.
It remains to establish that NormGraph 𝑝,𝑠 is 𝐾𝑠,𝑠!+1 -free. Once this is done, we can take 𝑝 to
be the largest prime at most 𝑛1/𝑠 , and then

𝑝 2𝑠−1 1
ex(𝑛, 𝐾𝑠,𝑠!+1 ) ≥ ex( 𝑝 𝑠 , 𝐾𝑠,𝑠!+1 ) ≥ ≥ − 𝑜(1) 𝑛2−1/𝑠 .
2 2
Proposition 1.10.10
NormGraph 𝑝,𝑠 is 𝐾 𝑠,𝑠!+1 -free for all 𝑠 ≥ 2.
We wish to upper bound the number of common neighbors to a set of 𝑠 vertices. This
amount to showing that a certain system of algebraic equations cannot have too many
solutions. We quote without proof the following key algebraic result from Kollár, Rónyai,
and Szabó (1996), which can be proved using algebraic geometry.
Theorem 1.10.11
Let F be any field and 𝑎 𝑖 𝑗 , 𝑏 𝑖 ∈ F such that 𝑎 𝑖 𝑗 ≠ 𝑎 𝑖′ 𝑗 for all 𝑖 ≠ 𝑖 ′ . Then the system of
equations
(𝑥 1 − 𝑎 11 ) (𝑥2 − 𝑎 12 ) · · · (𝑥 𝑠 − 𝑎 1𝑠 ) = 𝑏 1
(𝑥 1 − 𝑎 21 ) (𝑥2 − 𝑎 22 ) · · · (𝑥 𝑠 − 𝑎 2𝑠 ) = 𝑏 2
..
.
(𝑥1 − 𝑎 𝑠1 ) (𝑥2 − 𝑎 𝑠2 ) · · · (𝑥 𝑠 − 𝑎 𝑠𝑠 ) = 𝑏 𝑠
has at most 𝑠! solutions (𝑥1 , . . . , 𝑥 𝑠 ) ∈ F𝑠 .
Remark 1.10.12 (Special case 𝑏 = 0). Consider the special case when all the 𝑏 𝑖 are 0. In
this case, since the 𝑎 𝑖 𝑗 are distinct for each fixed 𝑗, every solution to the system corresponds
to a permutation 𝜋 : [𝑠] → [𝑠], setting 𝑥𝑖 = 𝑎 𝑖 𝜋 (𝑖) . So there are exactly 𝑠! solutions in
this special case. The difficult part of the theorem says that the number of solutions cannot
increase if we move 𝑏 away from the origin.
Proof of Proposition 1.10.10. Consider distinct 𝑦 1 , 𝑦 2 , . . . , 𝑦 𝑠 ∈ F 𝑝 𝑠 . We wish to bound the
number of common neighbors 𝑥. Recall that in a field with characteristic 𝑝, we have the
identity (𝑥 + 𝑦) 𝑝 = 𝑥 𝑝 + 𝑦 𝑝 for all 𝑥, 𝑦. So,
1 = 𝑁 (𝑥 + 𝑦 𝑖 ) = (𝑥 + 𝑦 𝑖 ) (𝑥 + 𝑦 𝑖 ) 𝑝 . . . (𝑥 + 𝑦 𝑖 ) 𝑝
𝑠−1
𝑠−1 𝑠−1
= (𝑥 + 𝑦 𝑖 ) (𝑥 𝑝 + 𝑦 𝑖𝑝 ) . . . (𝑥 𝑝 + 𝑦 𝑖𝑝 )
for all 1 ≤ 𝑖 ≤ 𝑠. By Theorem 1.10.11, these 𝑠 equations (as 𝑖 ranges over [𝑠]) have at most
𝑠! solutions in 𝑥. Note the hypothesis of Theorem 1.10.11 is satisfied since 𝑦 𝑖𝑝 = 𝑦 𝑝𝑗 if and
only if 𝑦 𝑖 = 𝑦 𝑗 in F 𝑝 𝑠 . □
Now we modify the norm graph construction to forbid 𝐾𝑠, (𝑠−1)!+1 , thereby yielding Theo-
rem 1.10.7.
Construction 1.10.13 (Projective norm graph)
Let ProjNormGraph 𝒑,𝒔 be the graph with vertex set F 𝑝 𝑠−1 × F×𝑝 , where two vertices
(𝑋, 𝑥), (𝑌 , 𝑦) ∈ F 𝑝 𝑠−1 × F×𝑝 are adjacent if and only if
𝑁 (𝑋 + 𝑌 ) = 𝑥𝑦.
In ProjNormGraph 𝑝,𝑠 , every vertex (𝑋, 𝑥) has degree 𝑝 𝑠−1 − 1 since its neighbors are
(𝑌 , 𝑁 (𝑋 + 𝑌 )/𝑥) for all 𝑌 ≠ −𝑋. There are ( 𝑝 𝑠−1 − 1) 𝑝 𝑠−1 ( 𝑝 − 1)/2 edges. As earlier, it
remains to show that this graph is 𝐾𝑠, (𝑠−1)!+1 -free. Once we know this, by taking 𝑝 to be the
largest prime satisfying 𝑝 𝑠−1 ( 𝑝 − 1) ≤ 𝑛, we obtain the desired lower bound

1 𝑠−1 1
ex(𝑛, 𝐾𝑠, (𝑠−1)!+1 ) ≥ ( 𝑝 − 1) 𝑝 ( 𝑝 − 1) ≥
𝑠−1
− 𝑜(1) 𝑛2−1/𝑠 .
2 2
Proposition 1.10.14
ProjNormGraph 𝑝,𝑠 is 𝐾 𝑠, (𝑠−1)!+1 -free.
Proof. Fix distinct (𝑌1 , 𝑦 1 ), . . . , (𝑌𝑠 , 𝑦 𝑠 ) ∈ F 𝑝 𝑠−1 × F×𝑝 . We wish to show that there are at most
(𝑠 − 1)! solutions (𝑋, 𝑥) ∈ F 𝑝 𝑠−1 × F×𝑝 to the system of equations
𝑁 (𝑋 + 𝑌𝑖 ) = 𝑥𝑦 𝑖 , 𝑖 = 1, . . . , 𝑠.
Assume this system has at least one solution. Then if 𝑌𝑖 = 𝑌 𝑗 with 𝑖 ≠ 𝑗 we must have
that 𝑦 𝑖 = 𝑦 𝑗 . Therefore all the 𝑌𝑖 are distinct. For each 𝑖 < 𝑠, dividing 𝑁 (𝑋 + 𝑌𝑖 ) = 𝑥𝑦 𝑖 by
𝑁 (𝑋 + 𝑌𝑠 ) = 𝑥𝑦 𝑠 gives

𝑋 + 𝑌𝑖 𝑦𝑖
𝑁 = , 𝑖 = 1, . . . , 𝑠 − 1.
𝑋 + 𝑌𝑠 𝑦𝑠
Dividing both sides by 𝑁 (𝑌𝑖 − 𝑌𝑠 ) gives

1 1 𝑦𝑖
𝑁 + = , 𝑖 = 1, . . . , 𝑠 − 1.
𝑋 + 𝑌𝑠 𝑌𝑖 − 𝑌𝑠 𝑁 (𝑌𝑖 − 𝑌𝑠 )𝑦 𝑠
Now apply Theorem 1.10.11 (same as in the proof of Proposition 1.10.10). We deduce
that there are at most (𝑠 − 1)! choices for 𝑋, and each such 𝑋 automatically determines
𝑥 = 𝑁 (𝑋 + 𝑌1 )/𝑦 1 . Thus, there are at most (𝑠 − 1)! solutions (𝑋, 𝑥). □
𝐶4 , 𝐶6 , 𝐶10 -free
Finally, let us turn to constructions of 𝐶2𝑘 -free graphs. We had mentioned in Section 1.6 that
ex(𝐶2𝑘 , 𝑛) = 𝑂 𝑘 (𝑛1+1/𝑘 ). We saw a matching lower bound construction for 4-cycles. Now
we give matching constructions for 6-cycles and 10-cycles. (It remains an open problem for
other cycle lengths.)
Theorem 1.10.15 (Tight lower bound for avoiding 𝐶2𝑘 for 𝑘 ∈ {2, 3, 5})
Let 𝑘 ∈ {2, 3, 5}. Then there is a constant 𝑐 > 0 such that for every 𝑛,
ex(𝑛, 𝐶2𝑘 ) ≥ 𝑐𝑛1+1/𝑘 .
Remark 1.10.16 (History). The existence of such 𝐶2𝑘 -free graphs for 𝑘 ∈ {3, 5} is due to
Benson (1966) and Singleton (1966). The construction given here is due to Wenger (1991),
with a simplified description due to Conlon (2021).
The following construction generalizes the point-line incidence graph construction earlier
for the 𝐶4 -free graph in Theorem 1.10.1. Here we consider a special set of lines in F𝑞𝑘 , whereas
previously for 𝐶4 we took all lines in F2𝑞 .
Construction 1.10.17 (𝐶2𝑘 -free construction for 𝑘 ∈ {2, 3, 5})

Let 𝑞 be a prime power. Let L denote the set of all lines in F𝑞𝑘 whose direction can
be written as (1, 𝑡, . . . , 𝑡 𝑘−1 ) for some 𝑡 ∈ F𝑞 . Let 𝐺 𝑞,𝑘 denote the bipartite point-line
incidence graph with vertex sets F𝑞𝑘 and L. That is, ( 𝑝, ℓ) ∈ F𝑞𝑘 × L is an edge if and
only if 𝑝 ∈ ℓ.
We have |L| = 𝑞 𝑘 , since to specify a line in L we can provide a point with first coordinate
equal to zero, along with a choice of 𝑡 ∈ F𝑞 giving the direction of the line. So the graph 𝐺 𝑞,𝑘
has 𝑛 = 2𝑞 𝑘 vertices. Since each line contains exactly 𝑞 points, there are exactly 𝑞 𝑘+1 ≍ 𝑛1+1/𝑘
edges in the graph. It remains to show that this graph is 𝐶2𝑘 -free whenever 𝑘 ∈ {2, 3, 5}.
Then Theorem 1.10.15 would follow after the usual trick of taking 𝑞 to be the largest prime
with 2𝑞 𝑘 < 𝑛.
Proposition 1.10.18
Let 𝑘 ∈ {2, 3, 5}. The graph 𝐺 𝑞,𝑘 from Construction 1.10.17 is 𝐶2𝑘 -free.
Proof. A 2𝑘-cycle in 𝐺 𝑞,𝑘 would correspond to 𝑝 1 , ℓ1 , . . . , 𝑝 𝑘 , ℓ𝑘 with distinct 𝑝 1 , . . . ,

𝑝 𝑘 ∈ F𝑞𝑘 and distinct ℓ1 , . . . , ℓ𝑘 ∈ L, and 𝑝 𝑖 , 𝑝 𝑖+1 ∈ ℓ𝑖 for all 𝑖 (indices taken mod 𝑘). Let
(1, 𝑡𝑖 , . . . , 𝑡 𝑖𝑘−1 ) denote the direction of ℓ𝑖 .
𝑝1 ℓ1 𝑝2
ℓ𝑘 ℓ2
𝑝𝑘 𝑝3
ℓ𝑘−1 ... ℓ3
Then
𝑝 𝑖+1 − 𝑝 𝑖 = 𝑎 𝑖 (1, 𝑡𝑖 , . . . , 𝑡 𝑖𝑘−1 )
for some 𝑎 𝑖 ∈ F𝑞 \ {0}. Thus (recall that 𝑝 𝑘+1 = 𝑝 1 )
∑︁
𝑘 ∑︁
𝑘
𝑎 𝑖 (1, 𝑡𝑖 , . . . , 𝑡 𝑖𝑘−1 ) = ( 𝑝 𝑖+1 − 𝑝 𝑖 ) = 0. (1.3)
𝑖=1 𝑖=1
The vectors (1, 𝑡𝑖 , . . . , 𝑡 𝑖𝑘−1 ), 𝑖 = 1, . . . , 𝑘, after deleting duplicates, are linearly independent.
One way to see this is via the Vandermonde determinant
1 𝑥1 𝑥12 ··· 𝑥 1𝑘−1
1 𝑥2 𝑥22 ··· 𝑥 2𝑘−1 Ö
.. .. .. .. .. = (𝑥 𝑗 − 𝑥𝑖 ).
. . . . . 𝑖< 𝑗
1 𝑥𝑘 𝑥 2𝑘 ··· 𝑥 𝑘𝑘−1
For (1.3) to hold, each vector (1, 𝑡𝑖 , . . . , 𝑡 𝑖𝑘−1 ) must appear at least twice in the sum, with
their coefficients 𝑎 𝑖 adding up to zero.
Since the lines ℓ1 , . . . , ℓ𝑘 are distinct, for each 𝑖 = 1, . . . , 𝑘 (indices taken mod 𝑘), the
lines ℓ𝑖 and ℓ𝑖+1 cannot be parallel. So, 𝑡 𝑖 ≠ 𝑡𝑖+1 . When 𝑘 ∈ {2, 3, 5} it is impossible to select
𝑡1 , . . . , 𝑡 𝑘 with no equal consecutive terms (including wraparound) and so that each value is
repeated at least twice. Therefore the 2𝑘-cycle cannot exist. (Why does the argument fail for
𝐶8 -freeness?) □
1.11 Randomized Algebraic Constructions

In this section, we show how to add randomness to algebraic constructions, thereby combining
the power of both approaches. This idea is due to Bukh (2015).
1.11 Randomized Algebraic Constructions 47
The algebraic constructions in the previous section can be abstractly described as follows.
Take a graph whose vertices are points in some algebraic set (e.g., some finite field geometry),
with two vertices 𝑥 and 𝑦 being adjacent if some algebraic relationship such as 𝑓 (𝑥, 𝑦) = 0
is satisfied. Previously, this 𝑓 was carefully chosen by hand. The new idea is to take 𝑓 to be
a random polynomial.
We illustrate this technique by giving another proof of the tightness of the KST bound on
extremal numbers for 𝐾𝑠,𝑡 when 𝑡 is large compared to 𝑠.
Theorem 1.11.1 (Tightness of KST bound for large 𝑡 )

For every 𝑠 ≥ 2, there exists some 𝑡 so that

1
ex(𝑛, 𝐾𝑠,𝑡 ) ≥ − 𝑜(1) 𝑛2−1/𝑠 .
2
The construction we present here has a worse dependence of 𝑡 on 𝑠 than in Theorem 1.10.7.
The main purpose of this section is to illustrate the technique of randomized algebraic
constructions. Bukh (2021) later gave a significant extension of this technique which shows
that ex(𝑛, 𝐾𝑠,𝑡 ) = Ω𝑠 (𝑛2−1/𝑠 ) for some 𝑡 close to 9𝑠 , improving on Theorem 1.10.7, which
required 𝑡 > (𝑠 − 1)!.
Proof idea. Take a random polynomial 𝑓 (𝑋1 , . . . , 𝑋𝑠 , 𝑌1 , . . . , 𝑌𝑠 ) symmetric in the 𝑋 and 𝑌
variables (i.e., 𝑓 (𝑋, 𝑌 ) = 𝑓 (𝑌 , 𝑋)), but otherwise uniformly chosen among all polynomials
with degree up to 𝑑 with coefficients in F𝑞 . Consider a graph with vertex set F𝑞𝑠 and where
𝑋 and 𝑌 are adjacent if 𝑓 (𝑋, 𝑌 ) = 0.
Given an 𝑠-vertex set 𝑈, let 𝑍𝑈 denote the set of common neighbors of 𝑈. It is an algebraic
set: the common zeros of the polynomials 𝑓 (𝑋, 𝑦), 𝑦 ∈ 𝑈. Due to the Lang–Weil bound
from algebraic geometry, 𝑍𝑈 is either bounded in size, |𝑍𝑈 | ≤ 𝐶 (the zero dimensional case),
or it must be quite large, say, |𝑍𝑈 | > 𝑞/2 (the positive dimensional case). This is unlike an
Erdős–Rényi random graph.
One can then deduce, using Markov’s inequality, that
𝑞 E[|𝑍𝑈 | 𝑘 ] 𝑂 𝑘 (1)
P(|𝑍𝑈 | > 𝐶) = P |𝑍𝑈 | > ≤ = ,
2 (𝑞/2) 𝑘 (𝑞/2) 𝑘
which is quite small (much smaller compared to an Erdős–Rényi random graph). So typically
very few sets 𝑈 have size > 𝐶. By deleting these bad 𝑈s from the vertex set of the graph, we
obtain a 𝐾𝑠,𝐶+1 -free graph with around 𝑞 𝑠 vertices and on the order of 𝑞 2𝑠−1 edges. ■
Now we begin the actual proof. Let 𝑞 be the largest prime power satisfying 𝑞 𝑠 ≤ 𝑛. Due
to prime gaps (Theorem 1.10.3), we have 𝑞 = (1 − 𝑜(1))𝑛1/𝑠 . So it suffices to construct a
𝐾𝑠,𝑡 -free graph on 𝑞 𝑠 vertices with (1/2 − 𝑜(1))𝑞 2𝑠−1 edges.
Let 𝑑 = 𝑠2 + 𝑠 (the reason for this choice will come up later). Let
𝑓 ∈ F𝑞 [𝑋1 , 𝑋2 , . . . , 𝑋𝑠 , 𝑌1 , 𝑌2 , . . . , 𝑌𝑠 ] ≤𝑑
be a polynomial chosen uniformly at random among all polynomials with degree at most
𝑑 in each of 𝑋 = (𝑋1 , 𝑋2 , . . . , 𝑋𝑠 ) and 𝑌 = (𝑌1 , 𝑌2 , . . . , 𝑌𝑠 ) and furthermore satisfying
𝑓 (𝑋, 𝑌 ) = 𝑓 (𝑌 , 𝑋). In other words,

∑︁
𝑓 = 𝑎 𝑖1 ,...,𝑖𝑠 , 𝑗1 ,..., 𝑗𝑠 𝑋1𝑖1 · · · 𝑋𝑠𝑖𝑠 𝑌1𝑗1 · · · 𝑌𝑠𝑗𝑠
𝑖1 +···+𝑖𝑠 ≤𝑑
𝑗1 +···+ 𝑗𝑠 ≤𝑑
where the coefficients 𝑎 𝑖1 ,...,𝑖𝑠 , 𝑗1 ,..., 𝑗𝑠 ∈ F𝑞 are chosen subject to 𝑎 𝑖1 ,...,𝑖𝑠 , 𝑗1 ,..., 𝑗𝑠 = 𝑎 𝑗1 ,..., 𝑗𝑠 ,𝑖1 ,...,𝑖𝑠
but otherwise independently and uniformly at random.
Let 𝐺 be the graph with vertex set F𝑞𝑠 , with distinct 𝑥, 𝑦 ∈ F𝑞𝑠 adjacent if and only if
𝑓 (𝑥, 𝑦) = 0.
Then 𝐺 is a random graph. The next two lemmas show that 𝐺 behaves in some ways like
a random graph with edges independently appearing with probability 1/𝑞. Indeed, the next
lemma shows that every pair of vertices form an edge with probability 1/𝑞.
Lemma 1.11.2 (Random polynomial)

Suppose 𝑓 is randomly chosen as above. For all 𝑢, 𝑣 ∈ F𝑞𝑠 ,
1
P[ 𝑓 (𝑢, 𝑣) = 0] = .
𝑞
Proof. Note that resampling the constant term of 𝑓 does not change its distribution. Thus,
𝑓 (𝑢, 𝑣) is uniformly distributed in F𝑞 for a fixed (𝑢, 𝑣). Hence 𝑓 (𝑢, 𝑣) takes each value with
probability 1/𝑞. □
More generally, we show below that the expected occurrence of small subgraphs mirrors
that of the usual random graph with independent edges. We write 𝑈2 for the set of unordered
pairs of element from 𝑈.
Lemma 1.11.3 (Random polynomial)

Suppose 𝑓 is randomly chosen as above. Let 𝑊 ⊆ F𝑞𝑠 with |𝑊 | ≤ 𝑑 + 1. Then the vector
(𝑊)
( 𝑓 (𝑢, 𝑣)) {𝑢,𝑣 } ∈ ( 𝑊 ) is uniformly distributed in F𝑞 2 . In particular, for any 𝐸 ⊆ 𝑊2 , one
2
has
P[ 𝑓 (𝑢, 𝑣) = 0 for all {𝑢, 𝑣} ∈ 𝐸] = 𝑞 − |𝐸 | .
Proof. We first perform multivariate Lagrange interpolation to show that ( 𝑓 (𝑢, 𝑣)) {𝑢,𝑣 } can
take all possible values. For each pair 𝑢, 𝑣 ∈ 𝑊 with 𝑢 ≠ 𝑣, we can find some polynomial
ℓ𝑢,𝑣 ∈ F[𝑋1 , . . . , 𝑋𝑠 ] of degree 1 such that ℓ𝑢,𝑣 (𝑢) = 1 and ℓ𝑢,𝑣 (𝑣) = 0. For each 𝑢 ∈ 𝑊, let
Ö
𝑞 𝑢 (𝑋) = ℓ𝑢,𝑣 (𝑋) ∈ F[𝑋1 , . . . , 𝑋𝑠 ]
𝑣 ∈𝑊\{𝑢}
which has degree |𝑊 | − 1 ≤ 𝑑. It satisfies 𝑞 𝑢 (𝑢) = 1, and 𝑞 𝑢 (𝑣) = 0 for all 𝑣 ∈ 𝑊 \ {𝑢}.
Let
∑︁
𝑝(𝑋, 𝑌 ) = 𝑐 𝑢,𝑣 (𝑞 𝑢 (𝑋)𝑞 𝑣 (𝑌 ) + 𝑞 𝑣 (𝑋)𝑞 𝑢 (𝑌 ))
{𝑢,𝑣 } ∈ ( 𝑊
2 )
with 𝑐 𝑢,𝑣 ∈ F𝑞 . Note that 𝑝(𝑋, 𝑌 ) = 𝑝(𝑌 , 𝑋). Also, 𝑝(𝑢, 𝑣) = 𝑐 𝑢,𝑣 for all distinct 𝑢, 𝑣 ∈ 𝑊.
Now let each 𝑐 𝑢,𝑣 ∈ F𝑞 above be chosen independently and uniformly at random so that
𝑝(𝑋, 𝑌 ) is a random polynomial. Note that 𝑓 (𝑋, 𝑌 ) and 𝑝(𝑋, 𝑌 ) are independent random
polynomials both with degree at most 𝑑 in each of 𝑋 and 𝑌 . Since 𝑓 is chosen uniformly
( |𝑊 |)
at random, it has the same distribution as 𝑓 + 𝑝. Since ( 𝑝(𝑢, 𝑣))𝑢,𝑣 = (𝑐 𝑢,𝑣 )𝑢,𝑣 ∈ F𝑞 2 is
uniformly distributed, the same must be true for ( 𝑓 (𝑢, 𝑣))𝑢,𝑣 as well. □
Now fix 𝑈 ⊆ F𝑞𝑠 with |𝑈| = 𝑠. We want to show that it is rare for 𝑈 to have many common
neighbors. We will use the method of moments. Let
𝑍𝑈 = the set of common neighbors of 𝑈
= {𝑥 ∈ F𝑞𝑠 \ 𝑈 : 𝑓 (𝑥, 𝑢) = 0 for all 𝑢 ∈ 𝑈}.
Then using Lemma 1.11.3, for any 𝑘 ≤ 𝑠2 + 1,
h ∑︁ 𝑘i
E[|𝑍𝑈 | 𝑘 ] = E 1{𝑣 ∈ 𝑍𝑈 }
∑︁
𝑣 ∈F𝑞𝑠 \𝑈
= E[1{𝑣 (1) , . . . , 𝑣 (𝑘 ) ∈ 𝑍𝑈 }]
∑︁
𝑣 (1) ,...,𝑣 (𝑘) ∈F𝑞𝑠 \𝑈
= P[ 𝑓 (𝑢, 𝑣) = 0 for all 𝑢 ∈ 𝑈 and 𝑣 ∈ {𝑣 (1) , . . . , 𝑣 (𝑘 ) }]

∑︁
𝑣 (1) ,...,𝑣 (𝑘) ∈F𝑞𝑠 \𝑈
𝑞 − |𝑈 | #{𝑣
(1)
,...,𝑣 (𝑘) }
= ,
𝑣 (1) ,...,𝑣 (𝑘) ∈F𝑞𝑠 \𝑈
with the final step due to Lemma 1.11.3 applied with 𝑊 = 𝑈 ∪ {𝑣 (1) , . . . , 𝑣 (𝑘 ) }, which has
cardinality ≤ |𝑈| + 𝑘 ≤ 𝑠 + 𝑠2 + 1 = 𝑑 + 1. Note that #{𝑣 (1) , . . . , 𝑣 (𝑘 ) } counts distinct elements
in the set. Thus, continuing the above calculation,
∑︁ 𝑞 𝑠 − |𝑈|
= 𝑞 −𝑟 𝑠 #{surjections [𝑘] → [𝑟]}
𝑟
∑︁
𝑟 ≤𝑘
≤ #{surjections [𝑘] → [𝑟]}

𝑟 ≤𝑘
= 𝑂 𝑘 (1).
Applying the preceding with 𝑘 = 𝑠2 + 1 and using Markov’s inequality, we get
2
𝑠 2 +1 𝑠 2 +1
E |𝑍𝑈 | 𝑠 +1 𝑂 𝑠 (1)
P(|𝑍𝑈 | ≥ 𝜆) = P(|𝑍𝑈 | ≥𝜆 )≤ 𝑠 2 +1
≤ 𝑠2 +1 . (1.4)
𝜆 𝜆
Remark 1.11.4. All the probabilistic arguments up to this point would be identical had we
used a random graph with independent edges appearing with probability 𝑝. In both settings,
|𝑍𝑈 | is a random variable with constant order expectation. However, their distributions are
extremely different, as we will soon see. For a random graph with independent edges, |𝑍𝑈 |
behaves like a Poisson random variable, and consequently, for any constant 𝑡, P(|𝑍𝑈 | ≥ 𝑡)
is bounded from below by a constant. Consequently, many 𝑠-element sets of vertices are
expected to have at least 𝑡 common neighbors, and so this method will not work. However,
this is not the case with the random algebraic construction. It is impossible for |𝑍𝑈 | to take
on certain ranges of values. If |𝑍𝑈 | is somewhat large, then it must be very large.
Note that 𝑍𝑈 is defined by 𝑠 polynomial equations. The next result tells us that the number
of points on such an algebraic variety must be either bounded or at least around 𝑞.
Lemma 1.11.5 (Dichotomy: number of common zeros)

For all 𝑠, 𝑑 there exists a constant 𝐶 such that if 𝑓1 (𝑋), . . . , 𝑓𝑠 (𝑋) are polynomials on F𝑞𝑠
of degree at most 𝑑, then
{𝑥 ∈ F𝑞𝑠 : 𝑓1 (𝑥) = . . . 𝑓𝑠 (𝑥) = 0}
√
has size either at most 𝐶 or at least 𝑞 − 𝐶 𝑞.
The lemma can be deduced from the following important result from algebraic geometry
due to Lang and Weil (1954), which says that the number of points of an 𝑟-dimensional
algebraic variety in F𝑞𝑠 is roughly 𝑞 𝑟 , as long as certain irreducibility hypotheses are satisfied.
We include here the statement of the Lang–Weil bound. Here F𝑞 denotes the algebraic closure
of F𝑞 .
Theorem 1.11.6 (Lang–Weil bound)

Let 𝑔1 , . . . , 𝑔𝑚 ∈ F𝑞 [𝑋] be polynomials of degree at most 𝑑. Let
n 𝑠
o
𝑉 = 𝑥 ∈ F𝑞 : 𝑔1 (𝑥) = 𝑔2 (𝑥) = . . . = 𝑔𝑚 (𝑥) .
Suppose 𝑉 is an irreducible variety. Then

𝑉 ∩ F𝑞𝑠 = 𝑞 dim 𝑉 (1 + 𝑂 𝑠,𝑚,𝑑 (𝑞 −1/2 )).
The two cases in Lemma 1.11.5 then correspond to the zero-dimensional case and the
positive-dimensional case, though some care is needed to deal with what happens if the
variety is reducible in the field closure. We refer the reader to Bukh (2015) for details on how
to deduce Lemma 1.11.5 from the Lang–Weil bound.
Now, continuing our proof of Theorem 1.11.1. Recall 𝑍𝑈 = {𝑥 ∈ F𝑞𝑠 \ 𝑈 : 𝑓 (𝑥, 𝑢) =
0 for all 𝑢 ∈ 𝑈}. Apply Lemma 1.11.5 to the polynomials 𝑓 (𝑋, 𝑢), 𝑢 ∈ 𝑈. Then for large
enough 𝑞 there exists a constant 𝐶 from Lemma 1.11.5 such that either |𝑍𝑈 | ≤ 𝐶 (bounded)
or |𝑍𝑈 | > 𝑞/2 (very large). Thus, by (1.4),
𝑞 𝑂 𝑠 (1)
P(|𝑍𝑈 | > 𝐶) = P |𝑍𝑈 | > ≤ .
2 (𝑞/2) 𝑠2 +1
So the expected number of 𝑠-element subset 𝑈 with |𝑍𝑈 | > 𝐶 is
𝑠
𝑞 𝑂 𝑠 (1)
≤ = 𝑂 𝑠 (1/𝑞).
𝑠 (𝑞/2) 𝑠2 +1
Remove from 𝐺 a vertex from every 𝑠-element 𝑈 with |𝑍𝑈 | > 𝐶. Then the resulting graph is
𝐾𝑠, ⌈𝐶 ⌉+1 -free. Since we remove at most 𝑞 𝑠 edges for each deleted vertex, the expected number
of remaining edges is at least

1 𝑞𝑠 1
− 𝑂 𝑠 (𝑞 𝑠−1 ) = − 𝑜(1) 𝑞 2𝑠−1 .
𝑞 2 2
Finally, given 𝑛, we can take the largest prime 𝑞 satisfying 𝑞 𝑠 ≤ 𝑛 to finish the proof of
Theorem 1.11.1.
Further Reading
Graph theory is a huge subject. There are many important topics that are quite far from
the main theme of this book. For a standard introduction to the subject (especially on more
classical aspects), several excellent graph theory textbooks are available: Bollobás (1998),
Bondy and Murty (2008), Diestel (2017), West (1996). The three-volume Combinatorial
Optimization by Schrĳver (2003) is also an excellent reference for graph theory, with a focus
on combinatorial algorithms.
The following surveys discuss in more depth various topics encountered in this chapter:
• The History of Degenerate (Bipartite) Extremal Graph problems by Füredi and Si-
monovits (2013);
• Hypergraph Turán Problems by Keevash (2011);
• Dependent Random Choice by Fox and Sudakov (2011).
Chapter Summary
• Turán number ex(𝑛, 𝐻) = the maximum number of edges in an 𝑛-vertex 𝐻-free graph.
• Turán’s theorem. Among all 𝑛-vertex 𝐾𝑟+1 -free graphs, the Turán graph 𝑇𝑛,𝑟 (a complete
𝑟-partite graph with nearly equal sized parts) uniquely maximizes the number of edges.
• Erdős–Stone–Simonovits Theorem. For any fixed graph 𝐻,
2
1 𝑛
ex(𝑛, 𝐻) = 1 − + 𝑜(1) .
𝜒(𝐻) − 1 2
• Supersaturation (from one copy to many copies): an 𝑛-vertex graph with ≥ ex(𝑛, 𝐻)+𝜀𝑛2
edges has ≥ 𝛿𝑛 𝑣 (𝐻 ) copies of 𝐻, for some constant 𝛿 > 0 only depending on 𝜀 > 0, and
provided that 𝑛 is sufficiently large.
• Kővári–Sós–Turán theorem. For fixed 𝑠 ≤ 𝑡,
ex(𝑛, 𝐾 𝑠,𝑡 ) = 𝑂 𝑠,𝑡 (𝑛2−1/𝑠 ).
– Tight for 𝐾2,2 , 𝐾3,3 , and more generally, for 𝐾 𝑠,𝑡 with 𝑡 much larger than 𝑠 (algebraic
constructions).
– Conjectured to be tight in general.
• Even cycles. For any integer 𝑘 ≥ 2,
ex(𝑛, 𝐶2𝑘 ) = 𝑂 𝑘 (𝑛1+1/𝑘 ).

– Tight for 𝑘 ∈ {2, 3, 5} (algebraic constructions).
– Conjectured to be tight in general.
• Randomized constructions for constructing 𝐻-free graphs: destroying all copies of 𝐻
from a random graph.
• Algebraic construction: define edges using polynomials over F𝑞𝑛 .
• Randomized algebraic constructions: randomly select the polynomials.
MIT OpenCourseWare
https://ocw.mit.edu
18.225 Graph Theory and Additive Combinatorics

Fall 2023
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.

mit18_225_f23_lec02-05

Uploaded by

Document Informationclick to expand document information

Document Informationclick to expand document information

Copyright:

Available Formats

mit18_225_f23_lec02-05

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

mit18_225_f23_lec02-05

Uploaded by

Copyright:

Available Formats

MIT OCW: Graph Theory and Additive Combinatorics --- Yufei Zhao

We begin by completely answering the following question.

Question 1.0.1 (Triangle-free graph)

Definition 1.0.2 (Extremal number / Turán number)

In this book, by 𝐻-free we always mean forbidding 𝐻 as a subgraph, rather than as

Question 1.0.3 (Turán problem)

1.1 Forbidding a Triangle: Mantel’s Theorem

Theorem 1.1.1 (Mantel’s theorem)

Using the notation of Definition 1.0.2, Mantel’s theorem says that

Therefore, deg 𝑥 + deg 𝑦 ≤ 𝑛, which implies that

1.1 Forbidding a Triangle: Mantel’s Theorem 13

Partition 𝑉 = 𝐴 ∪ 𝐵 where 𝐴 = 𝑁 (𝑣) and 𝐵 = 𝑉 \ 𝐴. Since 𝑣 is a vertex of maximum

The next exercise can be solved by a neat application of Mantel’s theorem.

1.2 Forbidding a Clique: Turán’s Theorem

Question 1.2.1 (𝐾𝑟+1 -free graph)

Construction 1.2.2 (Turán graph)

Example 1.2.3. 𝑇10,3 = 𝐾3,3,4 :

1.2 Forbidding a Clique: Turán’s Theorem 15

Turán (1941) proved the following fundamental result.

Theorem 1.2.4 (Turán’s theorem)

The first part of the theorem says that

Corollary 1.2.6 (Turán’s theorem)

Lemma 1.2.7 (Maximum number of edges in an 𝑟 -partite graph)

Let 𝐵 = 𝑉 \ 𝐴. Since 𝑣 is a vertex of maximum degree, we have deg 𝑥 ≤ deg 𝑣 = | 𝐴| for

1.2 Forbidding a Clique: Turán’s Theorem 17

Since 𝐺 is 𝐾𝑟+1 -free, every 𝑥 ∈ 𝐵 has at most 𝑟 − 1 neighbors in 𝐴. So

Therefore, nonadjacency is an equivalence relation among vertices of 𝐺. So the comple-

1.3 Turán Density and Supersaturation 19

1.3 Turán Density and Supersaturation

The claim then follows. □

Definition 1.3.2 (Turán density)

Here are some additional equivalent definitions of Turán density:

1.3 Turán Density and Supersaturation 21

Theorem 1.3.4 (Supersaturation)

Exercise 1.3.5 (Supersaturation for hypergraphs). Let 𝐻 be an 𝑟-uniform hypergraph

Exercise 1.3.7 (Density Szemerédi). Let 𝑘 ≥ 3. Assuming Szemerédi’s theorem for

1.4 Forbidding a Complete Bipartite Graph: Kővári–Sós–Turán Theorem

Problem 1.4.1 (Zarankiewicz problem)

Theorem 1.4.2 (Kővári–Sós–Turán theorem – “KST theorem”)

The proof proceeds by double counting.

1.4 Forbidding a Complete Bipartite Graph: Kővári–Sós–Turán Theorem 23

Theorem 1.4.3 (KST theorem)

Conjecture 1.4.4 (Tightness of KST bound)

Here is an easy consequence of the KST theorem.

Geometric Applications of the KST Theorem

Question 1.4.6 (Erdős unit distance problem)

1.4 Forbidding a Complete Bipartite Graph: Kővári–Sós–Turán Theorem 25

Conjecture 1.4.7 (Erdős unit distance conjecture)

Theorem 1.4.8 (Upper bound on the unit distance problem)

Question 1.4.9 (Erdős distinct distances problem)

Theorem 1.4.10 (Guth–Katz distinct distances theorem)

Show that lim 𝑘→∞ 𝑑 𝑘 (𝑆) exists and is always either 0 or 1.

1.5 Forbidding a General Subgraph: Erdős–Stone–Simonovits Theorem 27

1.5 Forbidding a General Subgraph: Erdős–Stone–Simonovits Theorem

Theorem 1.5.1 (Erdős–Stone–Simonovits theorem)

It suffices to establish the Erdős–Stone–Simonovits theorem for complete 𝑟-partite graphs

Theorem 1.5.5 (Erdős–Stone theorem)

Every 𝑟-tuple in 𝑉1 × · · · × 𝑉𝑟 is an edge.