Proof. Given $𝜀>0$, let $L=L\left(\frac{10}{𝜀},\frac{𝜀}{2}\right)$ and $\delta =\frac{{𝜀}^2}{2L}$ and apply Szemerédi Regularity Lemma with parameters $\frac{𝜀}{2}$ and $l=\frac{10}{𝜀}$. We define the graph on vertex set $\{V_1,\dots ,V_k\}$. Define the reduced graph $R_{𝜀,\frac{𝜀}{2}}$ on $V(R_{\alpha ,𝜀})=\{V_1,\dots ,V_k\}$ and $V_i\sim V_j$ if $i\ne j$, $\frac{𝜀}{2}$-uniform and $d(V_i,V_j)\ge 𝜀$.

Claim 1: $R_{𝜀,\frac{𝜀}{2}}$ is triangle-free.

If there exist $V_i,V_j,V_k$ distinct with

and are pairwise $\frac{𝜀}{2}$-uniform. Then consider

We know

so let $x\in V_i^{\prime }$.

Now let

Again this set is non-empty, so choose $y$ in it.

So now note,

So there exist $u,v\in N(x)\cap N(y)\cap V_k$ such that $uv\in G$. But then $x,y,u,v$ form a $K_4$, contradiction.

Claim 2: $d(V_i,V_j)\le \frac{1}{2}+2𝜀$, for all $i<j$.

Throw away $𝜀|V_i|$ vertices in $V_i$ with degree $<\frac{1}{2}+𝜀$ to $V_j$. There are at least $(1-2𝜀)\frac{n}{L}>\delta n$ vertices that remain in $V_i$. So there exist $u,v\in V_i$, $uv\in G$.

Now note

Now use independence number property to find $x,y\in N(u)\cap N(v)\cap V_i$ such that $xy\in G$. Then $x,y,u,v$ is a $K_4$, contradiction.

We now estimate the number of edges in $G$ using the claims.

Sketch. Let $d\to \infty$ slowly as $n\to \infty$. We consider the sphere $S^d$ in $d+1$ dimensions.

“join a red point to a blue point if they are reasonably close” (say having inner product bigger than some small quantity). “join red to red and join blue to blue if they have distance $\ge 2-\frac{𝜀}{\sqrt{d}}$.

A little more formally:

Let $d\to \infty$ slowly, and let $𝜀\to 0$ slowly.

• Partition $S^d$ into $\frac{n}{2}$ regions of equal measure and with diameter $\le \frac{1}{2\sqrt{d}}$.

• Let $R=\{x_1,\dots ,x_{\frac{n}{2}}\}$, $B=\{y_1,\dots ,y_{\frac{n}{2}}\}$ be a set of points, with one from each of these regions.

We define $G$ by

• $x\in R$, $y\in B$: $x\sim y$ when $|x-y|<\sqrt{2}-\frac{𝜀}{\sqrt{d}}$.

• $x,x^{\prime }\in R$: $x\sim x^{\prime }$ when $|x-y|\ge 2-\frac{𝜀}{\sqrt{d}}$.

• Same for $y,y^{\prime }\in B$

Properties:

• $e(G)=\frac{n^2}{8}+o(n^2)$.

  

  $x\sim y$ iff $⟨x,y⟩\ge \frac{c𝜀}{\sqrt{d}}$. Let’s imagine $x=\left(\frac{1}{\sqrt{d}},\dots ,\frac{1}{\sqrt{d}}\right)$.

  $$\mathbb{P}\left(\frac{1}{d}\sum _{i=1}^d{y}_i\ge \frac{c𝜀}{\sqrt{d}}\right).\text{(∗)}$$

  $\mathrm{Var}{y}_i\sim \frac{1}{d}$, $\mathrm{Var}{\sum }_{i=1}^d{y}_i\sim 1$. So ($\ast$) is $\approx \mathbb{P}(Z\ge c𝜀)=\frac{1}{2}-\mathrm{\Theta }(𝜀)$, where $Z\sim N(0,1)$. So every vertex has degree $\approx \frac{n}{4}$, so $e(G)\approx \frac{n^2}{8}$.

• Now we check it is $K_4$-free

  First note $G[R],G[B]$ are triangle-free. Let $x,y,z\in R$ and assume they form a $K_3$. Then

  $$\begin{array}{llll}\hfill 0& \le \parallel x+y+z{\parallel }^2& \hfill & \\ \hfill & =⟨x+y+z,x+y+z⟩& \hfill & \\ \hfill & =3+2(⟨x,y⟩+⟨y,z⟩+⟨x,z⟩)& \hfill & \\ \hfill & =9-(\parallel x-y{\parallel }^2+\parallel y-z{\parallel }^2+\parallel x-z{\parallel }^2)& \hfill & \\ \hfill & =9-3{\left(2-\frac{𝜀}{\sqrt{d}}\right)}^2& \hfill & \\ \hfill & <0& \hfill & \end{array}$$

  Contradiction.

  $G$ is $K_4$-free: consider $\parallel x+x^{\prime }-y-y^{\prime }\parallel$ where $x,x^{\prime }\in R$ and $y,y^{\prime }\in B$.

• Finally, we need to check $\alpha (G)=o(n)$. Let $I\subset V(G)$ be independent. Let $I^{\prime }\cap R$, and without loss of generality say $|I^{\prime }|\ge \frac{|I|}{2}$. Let

  $$S=\bigcup _{x\in I^{\prime }}{R}_x$$

  where $R_x$ are the regions that we broke the sphere into at the start. We have $\mu (S)=\frac{2|I^{\prime }|}{n}$ (where $\mu$ is such that $\mu (S^d)=1$). Note $S\subset S^d$ with diameter

  $$<2-\frac{c}{\sqrt{d}}.$$

  Fact from life: this implies $\mu (S)\to 0$ as $d\to \infty$.

  Hence $\frac{|I|}{n}\to 0$, i.e. $|I|=o(n)$.

Proof of Erdős, Klietman, Rothchild, 70s using Lemma 9.7. Let $𝜀>0$ be given. Then for large enough $n$,

Proof of Lemma 9.7. Given a graph $H$ on $[k]$ and a partition $[n]=V_1\cup \cdots \cup V_k$, we define $G$ to be the blow up of $H$ onte $\{V_i\}$ by $V(G)=[n]$ and include all of $V_i{V}_j$ into $G$ whenever $ij\in H$.

Let $𝜀>0$ be given. We define $G=G_{n,𝜀}$ to be all graphs formed in the following steps. Let $L=L\left(\frac{10}{𝜀},\frac{{𝜀}^2}{2}\right)$.

• (1) Let $H$ be a triangle-free graph on $[k]$ where $k\le l$.
• (2) Let $u[n]=V_1\cup \cdots \cup V_k$ be an equipartition, and blow up $H$ onto $\{V_i\}$.
• (3) Throw in ${𝜀}^2{n}^2$ edges in any way.

Check $|G|$ is small:

Each $G\in G$ can be made triangle-free by removing $\le 𝜀n^2$ edges: this is true by construction (in fact only need to remove ${𝜀}^2{n}^2$ edges).

Finally, we need to check that every triangle-free graph on $[n]$ is contained in some $G\in G$. We apply Szemerédi Regularity Lemma with parameter $l=\frac{10}{𝜀}$, $\frac{{𝜀}^2}{2}$, to get a partition $[n]=V_1\cup \cdots \cup V_k$ with $k\le L$. Consider the reduced graph $R=R_{{𝜀}^2,\frac{{𝜀}^2}{2}}$. Note $R$ is triangle-free. So use $G\subset R$ blown up to $\{V_1\}$ plus ${𝜀}^{2}n$ extra edges. □

Proof of Szemerédi Regularity Lemma. Given $𝜀,l$ and a graph $G$, we loop the following, iteratively refining a partition.

Start with $V(G)=V_1\cup \cdots \cup V_l$, arbitrarily into an equipartition. At a general step, we are given

an equipartition.

If there are $\le 𝜀\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ non $𝜀$-uniform pairs, then output ${\{V_i\}}_{i=1}^k$ and done So assume $>\left(\genfrac{}{}{0ex}{}{k}{2}\right)$. For each non $𝜀$-uniform pair $V_i,V_j$, we select $W_{ij}\subset V_i$, $W_{ji}\subset V_j$, $W_{ij}|,|W_{ji}|\ge 𝜀|V_i|$ and $|d(W_{ij},W_{ji})-d(V_i,V_j)|>𝜀$.

Now for each $V_i$ consider ${\{W_{ij}\}}_{i=1}^k$. Let

be a common refinement of these $\{W_{ij}\}$. We now refine this partition further to an equipartition where each cell has size $\frac{n}{k{4}^k}$ (this is a slight cheat $\ast$). Putting all these partitions together, we get

Now loop again with this partition.

Next step: show that this loop eventually terminates.

Analysis of Algorithm: We define the index of a partition $V_1,\dots ,V_k$ to be

We claim that as we go from $V_1,\dots ,V_k$ to $\{V_{ij}\}$, we increase the index by at least $+\frac{{𝜀}^5}{2}$. Fix $V_i$, $V_j$ and consider

Here we are using

Note $(\ast )\ge 0$. Now assume that $V_i$, $V_j$ are not $𝜀$-uniform. Define

So

So since the number of non $𝜀$-uniform pairs is $\ge \left(\genfrac{}{}{0ex}{}{k}{2}\right)$, we get an $+{𝜀}^4$ boost from $𝜀$ proportion of the parts. Also, the other pairs don’t hurt us. So index increases by $\ge \frac{{𝜀}^5}{2}$.

How to fix the tiny lie at $\ast$:

We can assume that we start the algorithm with $\gg \frac{1}{{𝜀}^2}$ parts. Now each time we encounter a “rounding issue”, we just throw out the remainder of the cell to some bin I track. At a given step, we throw out at most

Summing over all steps in algorithm, we still throw out at most $\ll 𝜀n$. We just redistribute these vertices equally at the end.

• This does not ruin the $𝜀$-uniformity: your new partition is at most $2𝜀$-uniform.

• Also need to check that throwing out these bits does not affect the calculations by more than a small amount. □