Proof of Erdős-Stone Theorem Part I

Erdős-Stone Theorem (1946): Fix $s,r\in\mathbb{N}$ and $c>0$. If $n$ is sufficiently large, then every $n$-vertex graph with $t_r(n)+cn^2$ edges contains $K_{r+1}[s]$.

A fundamental theorem in extremal graph theory. Note that $t_r(n)=(1-1/r)\frac{n^2}{2}-O(n)$, so it could also be replaced with $(1-1/r)\frac{n^2}{2}$.

The proof here follows the hints from Lovász L., Combinatorial problems and and exercises, 2nd ed. (North-Holland, 1993).

In this part, we show a weaker result.

Lemma

Fix $s,r\in\mathbb{N}$ and $\epsilon>0$. For sufficiently large $n$, every $n$-vertex graph with minimum degree at least $(1-1/r+\epsilon)n$ contains $K_{r+1}[s]$.

Proof

By induction on $r$. For $r=1$, every vertex has degree at least $\epsilon n$. There are $\binom{n}{s}$ $s$-sets in $V(G)$, and each vertex is fully connected to as least $\binom{\epsilon n}{s}$ $s$-sets. So for the lemma to hold when $r=1$, it suffices to show that $n\binom{\epsilon n}{s}/\binom{n}{s}\geq s$, which is simple.

In the induction step, let $t=\lceil\frac{s}{\epsilon}\rceil\geq s$. Suppose there exist $r$ disjoint $t$-sets $A_1,A_2,\ldots,A_r$ such that vertices from different $t$-sets are adjacent. Let $U=V(G)-\cup_{i=1}^rA_i$. We want to show that in $U$ there are sufficiently many vertices that are adjacent to at least $(r-1)t+s$ vertices in $V(G)-U$. Each of these vertices in $U$ must be fully connected to an $s$-set in each $A_i$, and the combinations of $r$ $s$-sets is $\binom{t}{s}^r$, which is finite.

Between $U$ and $V(G)-U$ there are at least $rt((1-\frac{1}{r}+\epsilon)n-(rt-1))$ edges, so on average each vertex in $U$ is adjacent to $\frac{rt((1-\frac{1}{r}+\epsilon)n-(rt-1))}{n-rt}$ vertices in $V(G)-U$. That expression, for sufficiently large $n$, is indeed at least $(r-1)t+s$. Hence there are at least $\frac{|U|}{1+t-s}=\frac{n-rt}{1+t-s}=\Theta(n)$ vertices in $U$ adjacent to at east $(r-1)t+s$ vertices in $V(G)-U$.

$\diamond$