Proof. We sample $x_1,\dots ,x_t\in V(G)$ uniformly at random (with replacement). Then

Let $Y$ be the random variable that counts the number of $\{y_1,\dots ,y_s\}\in {(N(x_1)\cap \cdots N(x_t))}^{(s)}$ with

Then

so

To finish, define $R$ to be $N(x_1)\cap \cdots \cap N(x_t)$ with a vertex deleted from each $\{y_1,\dots ,y_s\}\in {\left({\bigcap }_{i=1}^{t}N(x_i)\right)}^{(s)}$ with $|N(y_1)\cap \cdots \cap N(y_s)|<k$. Thus by assumption, we have

Proof. First inject $A\to R$. We now inductively place the vertices $B=\{y_1,\dots ,y_l\}$. Assume we have embedded $y_1,\dots ,y_i$ into $G$. To embed $y_{i+1}$, simply consider the $N(y_{i+1})$. These have been embedded inside of $R$ and thus have $\ge |V(H)|$ common neighbours. So there must be a choice for $y_{i+1}$ that does not clash with the previous choices. □

Proof of Füredi. Given $G$, $e(G)\ge C{n}^{2-\frac{1}{s}}$, we choose $C=2|H|$, and want to show $G\supset H$. By lemma, enough to find a $(s,|V(H)|)$-rich set of size $\ge |A|$. Let $h=|V(H)|$ and $t=s$. Then

as desired. □

Proof. Let $n=2^{10d}$ and let $\chi$ be a colouring of $K_n$. Let $G$ be the graph of the majority colour. So $e(G)\ge \frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge \frac{n^2}{8}$. So we apply Dependent Random Choice to find a $(d,2^d)$-rich set of size $\ge 2^d$. If $t=2d$, then

Then can finish using Lemma 6.7. □

Proof. Apply Dependent Random Choice and embedding Lemma 6.7 to the majority colour. □

Proof. We won’t prove. □

Proof of Lemma 6.13. For $x_1,\dots ,x_t$, $t<s$, let

Say that $(x_1,\dots ,x_t)$ is healthy if

Observation: If $x_1,\dots ,x_t$ is healthy, then the number of $y$ such that $(x_1,\dots ,x_t,y)$ is not healthy is $\le \frac{|U|}{2s}$.

Proof of observation:

Let $B_{x_1,\dots ,x_t}=\{y:(x_1,\dots ,x_t,y)\text{ is not healthy}\}$. Then

But if $|B_{x_1,\dots ,x_t}|>\frac{|U|}{2s}$, I contradict that $x_1,\dots ,x_t$ is healthy. So we have proved the observation.

We now inject $f:A\to U$ inductively. Assume we have embedded $a_1,\dots ,a_i$ so far. We assume that we have

is healthy for all $b\in B$. We now embed $a_{i+1}$. ulet $b_1,\dots ,b_s$ be the neighbour of $a_{i+1}$. We know $f(N(b_i)\cap \{a_1,..,a_i\})$ are healthy, so there are at most (by observation) $\le \frac{|U|}{2s}$ ways of choosing $f(a_{i+1})\in U$ so that one of the neighbours becomes unhealthy. But there are only $\le s$ neighbours. So there are $>\frac{|U|}{2}$ choices that maintain all healthy neighbours. Since $|U|>2k$, I can map $a_{i+1}$ to a new vertex.

We now inject $f:B\to V(G)$ exactly as we saw in the proof of Lemma 6.7. □

Proof of Lemma 6.14. Let $x_1,\dots ,x_s\in V(G)$ be chosen uniformly at random. Let $U=N(x_1)\cap \cdots \cap N(x_s)$. Let $X=|U|$. We have $𝔼X\ge {𝜀}^s\cdot n$.

Let $Y=|\{(y_1,\dots ,y_s)\in U^s:d(x_1,\dots ,x_s)<k\}|$. $𝔼Y\le n^s{\left(\frac{k}{n}\right)}^s$. Now note

So there is a $U$ such that

So $|U|\ge \frac{{𝜀}^{s}n}{2}>2k$.

Proof. Apply our second dependent random choice lemma (Lemma 6.14) to find an approximately $(d,k)$-rich set $U\subset V(G)$, with $|U|>2k$, where $G$ is the graph of the denser colour. Then apply the embedding lemma for approximately $(d,k)$-rich sets (Lemma 6.13) to find $G\supset H$. □

Proof. Let $B_i=\{x\in C_0:|N(x)\cap C_i|<p|C_i|\}$. Note

Hence $B_i<𝜀n$ for all $i$. So we must have

Proof of Embedding lemma for $(p,eps)$-dense graphs. Let $V(H)=\{x_1,\dots ,x_k\}$. We inductively map $x_i\to v_i$, $v_i\in V(G)$. At each stage we maintain a set of candidates for each $x_i$. In particular,

meaning after we have embedded $x_1\to v_1$, …, $x_i\to v_i$, we maintain that after embedding $x_1,\dots ,x_i$ we have

We also require

where $d_i(j)=|N(x_j)\cap \{x_1,\dots ,x_i\}|$.

Say at step $i$, I have mapped $x_1,\dots ,x_i$ preserving adjacencies and preserving ($\ast$) and ($\ast \ast$). We now choose $v_{i+1}$.

We want to choose $v_{i+1}\in C_i(i+1)$. Note

Let $C_0=C_i(i+1)\setminus \{v_1,\dots ,v_i\}$ and note

Now apply the observation with $C_0$ and $C_i(j_1),\dots ,C_i(j_d)$, where $x_i\sim x_{j_1},\dots ,x_{j_d}$, to find a vertex $v_{i+1}\in C_i(i+1)$ such that

and similarly up to

as desired. □

Proof of Lemma 6.20. Greedily embed $H$ into $G$. This is possible, because when we embed $x_{i+1}$, there are at least

many possible options (a lot!). □

Proof. We work by induction on $t$.

For $t=0$: trivial, can just take $A=G$.

Assume holds for $t-1$. Let $X,Y\subset V(G)$ such that

where $|X|,|Y|=\lceil 𝜀n\rceil$, because $G$ is not $(p,𝜀)$-dense.

If $|X\cap Y|\ge \frac{𝜀n}{2}$ then let $A^{\prime }=X\cap Y$, so

Throw away vertices of degree $\ge 16p|A^{\prime }|$ and we delete at most $\le \frac{1}{2}$ of $A^{\prime }$. Call the resulting set $A$, which is our desired set.

So we can assume that $|X\cap Y|\le \frac{𝜀n}{2}$. So we work with $X\setminus Y$ and $Y\setminus X$.

Fact: If I have a bipartite graph $G$ with partition $A\cup B$ and $e(G)\le p|A||B|$, then there exists $A_0\subset A$ with $|A_0|\ge \frac{|A|}{2}$ so that

for all $x\in A_0$.

Proof: Let $x\in A$ chosen uniformly at random. Then

So put

Let $X_0\subset X\setminus Y$ be such that

and $|X_0|\ge \frac{|X\setminus Y|}{2}\ge \frac{𝜀}{4}n$.

Now apply induction inside of $X_0$ to find $X_A\subset X_0$ with

and

Now consider the bipartite graph between $X_A$ and $Y\setminus X$. Note

So apply fact to find $Y_0\subset Y\setminus X$ with $|Y_0|\ge |Y\setminus X|$ and $|N(x)\cap X_A|\le 4p|X_A|$. Now apply induction inside of $Y_0$ to get $Y_A\subset Y_0$ satisfying the induction hypothesis.

Set $A=Y_A\cup X_A$. We now check the max degree condition. Let $x\in A$ and without loss of generality assume $x\in Y_A$.

Then

as desired. □

Proof of Graham, Rödl, Ruciński. Let $n>2^{Cd{(\log d)}^2}\cdot k$. Let $\chi$ be a 2-colouring of $K_n$. Set $p=\frac{1}{4d}$ and $𝜀=\frac{p^d}{4d}$, let $t=2{\log }_{2}d$.

Either there is a subset of $V(G)$ that is $(p,𝜀)$-dense with $\ge {\left(\frac{𝜀}{4}\right)}^{t}n$ vertices, in which case I apply Embedding lemma for $(p,eps)$-dense graphs to find $H$. Otherwise find a very dense subgraph in the other colour and apply the greedy embedding lemma (Lemma 6.20). □