$$

Adapted from lecture 3 of Yufei Zhao’s Fall 2019 class on “Graph theory and additive combinatorics” at MIT.

Say I give you some constant-size graph $H$ (e.g. a 4-clique, a 5-cycle) and tell you make a very dense graph $G$ that doesn’t contain $H$ as a subgraph.

If $H$ is not bipartite (i.e. it has an odd cycle), then this is super easy: all you need to do is to make $G$ bipartite. For example, you can make $G$ the complete bipartite graph $K_{\frac{n}{2},\frac{n}{2}}$, which has $\frac{n^2}{4}$ edges, so you get edge density $\approx 1/2$. Sometimes you can do even better than $1/2$, and the right answer is always known:

• When $H$ is an $(r+1)$-clique, Turán’s graph theorem pinpoints the exact number of edges you can get: about $(1-\frac{1}{r})\frac{n^2}{2}$.
• In general, the Erdős–Stone–Simonovits theorem tells you that the best edge density tends to $1-\frac{1}{\chi (H)-1}$ as $n$ grows, where $\chi (H)$ is the coloring number of $H$.

On the other hand, if $H$ is bipartite, then there is no “cheap trick” that allows you to avoid $H$. Indeed, even when $H$ is the complete bipartite graph $K_{s,t}$, we’ll see that the edge density will tend to $0$ as $n$ grows. More precisely, the Kővári–Sós–Turán theorem says that

$$m\le O\left(t^{1/s}{n}^{2-1/s}\right)=O\left(n^{2-1/s}\right),$$

which is strongly subquadratic! As we’ll see in the lower bounds section, this is mostly tight.

The idea is that forbidding $K_{s,t}$ puts a cap on the number of $s$-stars¹ in $G$, and that you cannot have high density without creating many $s$-stars.

Proof

The proof works by upper and lower bounding the number of $s$-stars in $G$.

For an upper bound, we can count $s$-stars by enumerating through all choices $S\in (\genfrac{}{}{0ex}{}{[n]}{s})$ of the $s$ “ends” of the star, then enumerating the choices of the center. Since $G$ is $K_{s,t}$-free, for any fixed $S$, there must be $<t$ possible choices for the center, so

$$\mathrm{\#}s\text{-stars}<t(\genfrac{}{}{0ex}{}{n}{s}).$$

(This is roughly $O(n^s)$; without restrictions, $G$ could have had as many as $(n-s)(\genfrac{}{}{0ex}{}{n}{s})\ge \mathrm{\Omega }(n^{s+1})$ $s$-stars, so this upper bound is actually quite stringent! The factor $n$ that separates these two expressions is exactly what will give the $n^{1/s}$ loss in the number of edges.)

For the lower bound, we start out by computing the number of $s$-stars as a function of the degrees $d(u)$ of each node:

$$\mathrm{\#}s\text{-stars}=\sum _u(\genfrac{}{}{0ex}{}{d(u)}{s}).$$

Now, it seems like for some fixed average degree $D$, the best way to minimize the number of $s$-stars is to have all degrees equal: indeed, if we let some degrees get bigger, then those nodes would produce proportionally many more $s$-stars. Formally, since $(\genfrac{}{}{0ex}{}{d(u)}{s})$ is convex² in $d(u)$, we have

$$\mathrm{\#}s\text{-stars}=\sum _u(\genfrac{}{}{0ex}{}{d(u)}{s})\ge n(\genfrac{}{}{0ex}{}{D}{s}).$$

Putting the bounds together, we get

$$\begin{array}{rlrl}& & n(\genfrac{}{}{0ex}{}{D}{s})& \le t(\genfrac{}{}{0ex}{}{n}{s})\\ & \Rightarrow & n{\left(\frac{D}{s}\right)}^s& \le t\cdot O{\left(\frac{n}{s}\right)}^s\\ & \Rightarrow & D& \le O\left(t^{1/s}{n}^{1-1/s}\right).\end{array}$$

Lower bounds

The $m\le O(n^{2-1/s})$ bound is believed to be tight, but surprisingly, matching constructions are only known in a few cases.

Probabilistic constructions

Let $v(H)$, $e(H)$ be the number of vertices and edges in the graph $H$ you want to forbid. Take an Erdős-Rényi random graph $G$ with edge probability $p$. There are $\le n^{v(H)}$ possible “sites”³ where $H$ could appear, and for each of them, the probability that it appears is $p^{e(H)}$. So if we make sure that

$$n^{v(H)}{p}^{e(H)}\le 1/2\stackrel{\sim }{\iff }p\le n^{-\frac{v(H)}{e(H)}},$$

then with constant probability we’ll get an $H$-free graph with $\mathrm{\Omega }(p{n}^2)=\mathrm{\Omega }\left(n^{2-\frac{v(H)}{e(H)}}\right)$ edges.⁴

For $K_{s,t}$ (with $s\le t$), this gives $\mathrm{\Omega }\left(n^{2-\frac{s+t}{st}}\right)\ge \mathrm{\Omega }(n^{2-2/s})$, so $n^{2-\mathrm{\Theta }(1/s)}$ is the right answer. In fact, when $t$ tends to infinity, we get $n^{2-\frac{1+o(1)}{s}}$, so the constant in the numerator is tight. Unfortunately though, the exponent is not exactly right for any $s,t\ge 2$.

Algebraic constructions

There are algebraic constructions that give the right exponent for some specific values of $s,t$.

Points and lines: $s=t=2$

Let $G$ be the (bipartite) graph of incidences between points and lines in ${\mathbb{Z}}_p^2$. This graph has $n=\mathrm{\Theta }(p^2)$ vertices and $\mathrm{\Theta }(p^3)=\mathrm{\Theta }(n^{3/2})$ edges. Since two distinct lines cannot meet at two distinct points, there is no $K_{2,2}$.

Spheres and points: $s=t=3$

This time, consider incidences between points and “spheres” of a fixed radius in ${\mathbb{Z}}_p^3$. It’s not super clear what a “sphere” is in ${\mathbb{Z}}_p^3$, but at least in Euclidean space, three distinct spheres of the same radius cannot meet at three distinct points, so there is no $K_{3,3}$. When the radius is chosen well, this graph has $n=\mathrm{\Theta }(p^3)$ vertices and $\mathrm{\Theta }(p^5)=\mathrm{\Theta }(n^{5/3})$ edges.

General: Alon–Kollár–Rónyai–Szabó

In general, for $t\ge (s-1)!+1$, there are $K_{s,t}$-free graphs with $\mathrm{\Omega }(n^{2-1/s})$ edges. But the answer remains unknown (everywhere?) when $s\le t\le (s-1)!$.

1. A graph where one node is linked to $s$ other nodes. ↩

2. To make this completely formal, we can extend $(\genfrac{}{}{0ex}{}{x}{s})$ to real values of as $\frac{x(x-1)\cdots (x-s+1)}{s!}$ for $x\ge s-1$, and let $(\genfrac{}{}{0ex}{}{x}{s}):=0$ when $x<s-1$. ↩

3. i.e. choices for where each vertex of this copy of $H$ lies in $G$ ↩

4. This can be slightly improved to $\mathrm{\Omega }\left(n^{2-\frac{v(H)-2}{e(H)-1}}\right)$ by allowing as many as $\approx \frac{p{n}^2}{4}$ copies of $H$ to appear in $G$ at first, and then remove them by taking an edge away from each (this is called the “alteration method”). However, this exponent is still not tight, so who cares. ↩