Proof sketch. Let $n\ge 4^k$ and let $\chi$ be a colouring of $K_n$. Pick a vertex $v$. It must have $\ge \frac{1}{2}n$ neighbours connected to it by the same colour.

Now ignore everything that was connected using the other colour. Pick a new vertex from what remains, and apply the process again:

We continue until either $A$ or $B$ gets to size $k$. We basically just want

$$n{\left(\frac{1}{2}\right)}^k{\left(\frac{1}{2}\right)}^k\ge 1,$$

i.e. $n\ge 4^k$. □

Proof. Let $n=(1-o(1))\frac{k}{\sqrt{2}e}{e}^{k∕2}$ we choose $\chi$ to be a random colouring of $E(K_n)$ where the colour of each edge is chosen red / blue uniformly and independently. We have

$$\begin{array}{llll}\hfill \mathbb{P}(\chi \text{ has a monochromatic }{K}_k)& =\mathbb{P}\left(\bigcup _{K\in {[n]}^{(k)}}\{K\text{ is a monochromatic clique}\}\right)& \hfill & \\ \hfill & \le 2\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}& \hfill & \\ \hfill & \le 2{\left(\frac{en}{k}\right)}^k{2}^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}& \hfill & \\ \hfill & =\left(\frac{en}{k}{2}^{\left(\frac{k-1}{2}\right)}\right)& \hfill & \\ \hfill & <1& \hfill & \end{array}$$

by the choice of $n$. □

Proof. Induction. See e.g. GT. □

Proof sketch. Sample $G\sim G(n,p)$, then define $\tilde{G}=G-(\text{a vertex from each triangle})$. For this to work we need $\frac{\#\text{vertices}}{2}>\#\text{triangles}$. So $\frac{n}{2}>p^3\left(\genfrac{}{}{0ex}{}{n}{3}\right)$. So take $p\sim n^{-2∕3}$. □

Proof. Let $k=(2+\delta )\frac{\log <!--FUNCTION\; APPLICATION-->np}{p}$, for some $\delta >0$. Let $X$ be the random variable that counts the number of independent $k$ sets in $G$.

$$\begin{array}{llll}\hfill 𝔼X& =𝔼\sum _{I\in {[n]}^{(k)}}{𝟙}_{I\text{ is }\text{independent<!--tex4ht:ref: gls@ind -->}}& \hfill & \\ \hfill & =\sum _{I\in {[n]}^{(k)}}\mathbb{P}(I\text{ is }\text{independent<!--tex4ht:ref: gls@ind -->})& \hfill & \\ \hfill & =\left(\genfrac{}{}{0ex}{}{n}{k}\right){(1-p)}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}& \hfill & \\ \hfill & \le {\left(\frac{en}{k}\right)}^k{e}^{-p\left(\genfrac{}{}{0ex}{}{k}{2}\right)}& \hfill & \\ \hfill & \le {\left(\frac{en}{k}\cdot e^{-\left(\frac{k-1}{2}\right)p}\right)}^k& \hfill & \\ \hfill & \to 0& \hfill & \end{array}$$

by plugging in $k$. So by Markov

$$\mathbb{P}(X\ge 1)\le 𝔼X\to 0.\square$$

Proof. Let $X$ be the random variable counting the number of triangles in $G$. Note

$$X=\sum _{T\in {[n]}^{(3)}}{𝟙}_{T^{(2)}\subset G}.$$

Mean is straightforward:

$$𝔼X=p^3\left(\genfrac{}{}{0ex}{}{n}{3}\right).$$

Variance is a little more tricky. First:

$$X^2=\sum _{S,T\in {[n]}^{(3)}}{𝟙}_{S^{(2)},T^{(2)}\subset G}.$$

We can write

$$\begin{array}{llll}\hfill 𝔼X^2& =\sum _{S,T\in {[n]}^{(2)}}\mathbb{P}(T^{(2)},S^{(2)}\subset G)& \hfill & \\ \hfill {(𝔼X)}^2& =\sum _{S,T\in {[n]}^{(2)}}\mathbb{P}(T^{(2)}\subset G)\mathbb{P}(S^{(2)}\subset G)& \hfill & \\ \hfill & & \hfill \end{array}$$

Since the pairs of events are independent whenever $|S^{(2)}\cap T^{(2)}|=0$, we have

$$\begin{array}{llll}\hfill \mathrm{Var}<!--FUNCTION\; APPLICATION-->X& \le \sum _{\begin{array}{c}S,T\in {[n]}^{(2)}\\ |S^{(2)}\cap T^{(2)}|=1\end{array}}& \hfill & \\ \hfill & \le p^5{n}^4+𝔼X& \hfill & \end{array}$$ Now note $$\begin{array}{llll}\hfill \mathbb{P}(|X-𝔼X|\ge \delta 𝔼X)& \le \frac{\mathrm{Var}<!--FUNCTION\; APPLICATION-->X}{{\delta }^2{(𝔼X)}^2}& \hfill & \\ \hfill & \le \frac{p^5{n}^4}{{\delta }^2{(𝔼X)}^2}+\frac{1}{{\delta }^2𝔼X}& \hfill & \\ \hfill & \le C\frac{p^5{n}^4}{{(n^3{p}^3)}^2}+\frac{1}{{\delta }^2𝔼X}& \hfill & \\ \hfill & \le C\frac{1}{n^{2}p}+\frac{1}{{\delta }^2𝔼X}& \hfill & \\ \hfill & \to 0& \hfill & \end{array}$$ □

Proof of lower bound on $R(3,k)$. Set $n={\left(\frac{k}{\log <!--FUNCTION\; APPLICATION-->k}\right)}^{3∕2}$, $p=n^{-2∕3}$. Let $G\sim G(n,p)$ and let $\tilde{G}$ with a vertex deleted from each triangle. Then with high probability we have

$$\begin{array}{llll}\hfill \alpha (\tilde{G})& \le \alpha (G)& \hfill & \\ \hfill & \le (2+o(1))\frac{\log <!--FUNCTION\; APPLICATION-->np}{p}& \hfill & \\ \hfill & \le \left(\frac{2}{3}+o(1)\right)n^{2∕3}\log <!--FUNCTION\; APPLICATION-->n& \hfill & \\ \hfill & \le \left(\frac{2}{3}+o(1)\right)\frac{k}{\log <!--FUNCTION\; APPLICATION-->k}(\log <!--FUNCTION\; APPLICATION-->k^{3∕2})& \hfill & \\ \hfill & \le (1+o(1))k& \hfill \text{(}\ast \text{) }\end{array}$$

We also have with high probability:

$$\begin{array}{llll}\hfill |V(\tilde{G})|& \ge n-(\#\text{of triangles in }G)& \hfill & \\ \hfill & \ge n-(1+o(1))\frac{p^3{n}^3}{6}& \hfill & \\ \hfill & =n-(1+o(1))\frac{n}{6}& \hfill & \\ \hfill & \ge \frac{n}{2}& \hfill \text{(}\ast \ast \text{) }\end{array}$$

So with high probability ($\ast$) and ($\ast \ast$) hold. So there must exist a graph $\tilde{G}$ on $\frac{n}{2}=\frac{1}{2}{\left(\frac{k}{\log <!--FUNCTION\; APPLICATION-->k}\right)}^{3∕2}$ with no triangles and independence number $<k$ (actually not quite, but would have worked if we multiply one of the parameters by a constant or something). □

Proof. Fix $t=\frac{p{k}^2}{16}$ and fix a set $S$ with size $|S|=k$.

$$\begin{array}{llll}\hfill \mathbb{P}(e(G[S])<t)& \le \sum _{i=0}^t\left(\genfrac{}{}{0ex}{}{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}{i}\right)p^i{(1-p)}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)-i}& \hfill & \\ \hfill & \le t\left(\genfrac{}{}{0ex}{}{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}{t}\right)p^t{(1-p)}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)-t}& \hfill & \\ \hfill & \le t\left[{\left(\frac{e{k}^2}{2t}\right)}^t{p}^t\right]e^{-p\left[\left(\genfrac{}{}{0ex}{}{k}{2}\right)-t\right]}& \hfill & \\ \hfill & \le t{(e8)}^{\frac{p{k}^2}{16}}{e}^{-p\left(\genfrac{}{}{0ex}{}{k}{2}\right)∕2}& \hfill & \\ \hfill & \le k^2{\left[{(e8)}^1{e}^{-4+o(1)}\right]}^{\frac{p{k}^2}{16}}& \hfill & \\ \hfill & \le e^{-\alpha p{k}^2}& \hfill & \end{array}$$

for some $\alpha >0$.

We now union bound on all $S\in {[n]}^{(k)}$.

$$\begin{array}{llll}\hfill \mathbb{P}(\exists <!--FUNCTION\; APPLICATION-->S\in {[n]}^{(k)}\text{ such that }e([S])<t)& \le \left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathbb{P}(e(G[S])<t)& \hfill & \\ \hfill & \le {\left(\frac{en}{k}\right)}^k{e}^{-\alpha k^{2}p}& \hfill & \\ \hfill & ={\left(\frac{en}{k}\cdot e^{-\alpha kp}\right)}^k& \hfill & \\ \hfill & \le {\left(enp{\left(\frac{1}{pn}\right)}^{\alpha C}\right)}^k& \hfill & \end{array}$$

(using $kp\ge C\log <!--FUNCTION\; APPLICATION-->n$) which $\to 0$ for $C>\frac{1}{\alpha }$. □

Proof. Let $I=\{(A_{i_1},\dots ,A_{i_k}):A_{i_1},\dots ,A_{i_k}\text{ are independent}\}$.

$$\begin{array}{llll}\hfill {𝟙}_{E_t}& \le \frac{1}{t!}\sum _{(A_{i_1},\dots ,A_{i_k}\in I}{𝟙}_{A_{i_1}\cap \cdots \cap A_{i_k}}& \hfill & \\ \hfill \mathbb{P}(E_t)& \le \sum _{(A_{i_1},\dots ,A_{i_k})\in I}\mathbb{P}(A_{i_1}\cap \cdots \cap A_{i_k})& \hfill & \\ \hfill & \le \frac{1}{t!}\sum _{i_1,\dots ,i_t}\mathbb{P}(A_{i_1})\cdots \mathbb{P}(A_{i_k})& \hfill & \\ \hfill & =\frac{1}{t!}{\left(\sum _i\mathbb{P}(A_i)\right)}^t\square & \hfill & \end{array}$$

Proof. Let $n$ be large. Let $p=\frac{\gamma }{\sqrt{n}}$ for some $\gamma >0$. Let $G\sim G(n,p)$, and let $\tilde{G}$ be $G$ with a maximal collection of edge disjoint triangles $T$ removed, i.e. $\tilde{G}=G-T$.

Clearly $\tilde{G}$ is triangle-free. We let $Q$ be the event that every set of size $k$, where $k=C\sqrt{n}\log <!--FUNCTION\; APPLICATION-->n$ contains at least $\frac{p{k}^2}{16}$ edges. We now consider

$$\mathbb{P}(\alpha (\tilde{G})\ge k)=\mathbb{P}(\alpha (\tilde{G})\ge k\cap Q)+\mathbb{P}(\alpha (\tilde{G})\ge k\cap Q^c).$$

So

$$\mathbb{P}(\alpha (\tilde{G})\ge k)\le \underset{(\ast )}{\underbrace{\mathbb{P}(\alpha (\tilde{G})\ge k\cap Q)}}+o(1).$$

We now union-bound

$$\begin{array}{llll}\hfill (\ast )& \le \left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathbb{P}(I\text{ independent in }\tilde{G}\cap Q)& \hfill & \\ \hfill & =\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathbb{P}(T\text{ intersects }I\text{ in }\ge \frac{p{k}^2}{16}\text{ edges})& \hfill & \end{array}$$

Define $\{T_i\}$ to be the collection of all triangles that meet $I$ in at least one edge, and define the event $A_i=\{T_i\subset G\}$.

Note that the event $E_t$, where $t=\frac{p{k}^2}{16}$, from the lemma holds on the event that $T$ meets $I$ in $\frac{p{k}^2}{16}$ edges. This is where we use the fact that we only choose edge-disjoint triangles! By Lemma 2.6, we have

$$\begin{array}{llll}\hfill \mathbb{P}(E_t)& \le 2{\left(\frac{e{k}^{2}n{p}^3}{t}\right)}^t& \hfill & \\ \hfill & \le {\left(\frac{16e{k}^{2}n{p}^3}{p{k}^2}\right)}^{\frac{p{k}^2}{16}}& \hfill & \\ \hfill & ={(16e{\gamma }^2)}^{\frac{p{k}^2}{16}}& \hfill & \end{array}$$

So

$$(\ast )\le {(16e{\gamma }^2)}^{\frac{p{k}^2}{16}}{\left(\frac{en}{k}\right)}^k\to 0,$$

if $\gamma$ is chosen to be small and $C$ large. □

Proof. Let $\delta >0$ and let $n=(1-\delta )\frac{\sqrt{2}k}{e}{2}^{k∕2}$. Choose a colouring uniformly at random. For every $S\in {[n]}^{(k)}$, define the event

$$A_S=\text{“}{S}^{(2)}\text{ are monochromatic”}.$$

We clearly have $\mathbb{P}(A_S)=2^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)+1}$.

Let $G$ be the dependency graph on ${\{A_S\}}_S$ where $A_S\sim A_T$ if $S^{(2)}\cap T^{(2)}\ne \varnothing$.

$$\mathrm{\Delta }=\mathrm{\Delta }(G)\le \left(\genfrac{}{}{0ex}{}{k}{2}\right)\cdot \left(\genfrac{}{}{0ex}{}{n-2}{k-2}\right)\le k^4\cdot \left(\frac{1}{n^2}\right)\left(\genfrac{}{}{0ex}{}{n}{k}\right)$$

We now check:

$$\mathrm{\Delta }\cdot 2^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)+1}\le 2k^4\left(\frac{1}{n^2}\right){\left(\frac{en}{k}\right)}^k{2}^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}={\left[(1+o(1))\frac{1}{n^{2∕k}}\left(\frac{en\sqrt{n}}{k}\cdot 2^{-k∕2}\right)\right]}^k.$$

This $\to 0$. So the condition in Local Lemma holds for sufficiently large $k$. □

Proof. We choose our colouring of the ground set $X$ uniformly at random. For each $e\in H$, define the event

$$A_e=\text{“}e\text{ monochromatic”}.$$

We have $\mathbb{P}(E_e)=2^{-k+1}$. We want $2^{-k+1}\le \frac{1}{e(\mathrm{\Delta }+1)}$. Note if we define our dependency graph $G$ by $A_e\sim A_f$ if $e\cap f\ne \varnothing$, then

$$\mathrm{\Delta }(G)\le d\cdot k.$$

Now just use the bound on $d$ in the hypothesis. □

Proof. We use

$$\mathbb{P}(A\cap B)=\mathbb{P}(A|B)\mathbb{P}(B).$$

Applying this many times, we have

$$\begin{array}{llll}\hfill \mathbb{P}\left(\bigcap _{i=1}^n{A}_i^c\right)& =\prod _{i=1}^n\mathbb{P}(A_i^c|A_1^c\cap \cdots \cap A_{i-1}^c)& \hfill & \\ \hfill & =\prod _{i=1}^n(1-\underset{\le x_i?}{\underbrace{\mathbb{P}(A_i|A_1^c\cap \cdots \cap A_{i-1}^c)}})& \hfill & \end{array}$$

We will prove that this term is $\le x_i$ by instead proving the more general statement:

$$(\ast )=\mathbb{P}\left(A_i | \bigcap _{j\in S}{A}_j^c\right)\le x_i,$$

where $S\subset [n]\setminus \{j\}$. We prove by induction on $|S|$.

If $S=\varnothing$, then done by hypothesis.

If $S\ne \varnothing$, then define

$$D=\bigcap _{\begin{array}{c}j\in S\\ j\sim i\end{array}}{A}_j^c,I=\bigcap _{j\in Sj⁄\sim i}{A}_j^c.$$

Note that

$$\begin{array}{llll}\hfill (\ast )& =\mathbb{P}(A_i|D\cap I)& \hfill & \\ \hfill & =\frac{\mathbb{P}(A_i\cap D\cap I)}{\mathbb{P}(D\cap I)}& \hfill & \\ \hfill & \le \frac{\mathbb{P}(A_i\cap I)}{\mathbb{P}(D\cap I)}& \hfill & \\ \hfill & =\frac{\mathbb{P}(A_i)\mathbb{P}(I)}{\mathbb{P}(D\cap I)}& \hfill & \\ \hfill & =\frac{\mathbb{P}(A_i)}{\mathbb{P}(D|I)}& \hfill & \end{array}$$

Let $\{A_{i_1},\dots ,A_{i_s}\}$ be the events in the intersection $D$. Then

$$\begin{array}{llll}\hfill \mathbb{P}(D|I)& =\prod _{j=1}^s\mathbb{P}(A_{i_j}^c|I\cap A_{i_1}^c\cap \cdots \cap A_{i_{j-1}}^c)& \hfill & \\ \hfill & =\prod _{j=1}^s(1-\mathbb{P}(A_{i_j}|I\cap A_{i_1}^c\cap \cdots \cap A_{i_{j-1}}^c))& \hfill & \end{array}$$

If no events in the intersection, then we are already done. Otherwise, we may apply the induction hypothesis to each term to get

$$\frac{\mathbb{P}(A_i)}{\mathbb{P}(D|I)}\le \frac{x_i\prod _{j\sim i}(1-x_j)}{\prod _{j=1}^s(1-x_{i_j})}\le x_i.\square$$

Proof of Local Lemma. Apply Lopsided Local Lemma with weights $x_i=\frac{1}{\mathrm{\Delta }+1}$ for all $i$. We just need to check that the probability upper bounds in Lopsided Local Lemma hold.

By calculus, we have

$${\left(\frac{\mathrm{\Delta }}{\mathrm{\Delta }+1}\right)}^{\mathrm{\Delta }}\ge \frac{1}{e}.$$

Hence

$$\begin{array}{llll}\hfill \mathbb{P}(A_i)& \le \frac{1}{e(\mathrm{\Delta }+1)}& \hfill & \\ \hfill & \le \frac{1}{\mathrm{\Delta }+1}{\left(\frac{\mathrm{\Delta }}{\mathrm{\Delta }+1}\right)}^{\mathrm{\Delta }}& \hfill & \\ \hfill & =\frac{1}{\mathrm{\Delta }+1}{\left(1-\frac{1}{\mathrm{\Delta }+1}\right)}^{\mathrm{\Delta }}& \hfill & \\ \hfill & \le \frac{1}{\mathrm{\Delta }+1}\prod _{A_i\sim A_j}\left(1-\frac{1}{\mathrm{\Delta }+1}\right)\square & \hfill & \end{array}$$

Proof of $R(3,k)\ge c\frac{k^2}{{(\log <!--FUNCTION\; APPLICATION-->k)}^2}$ using Local Lemma. Recall that it is enough to show that for sufficiently large $n$, there exists a triangle -free graph on $n$ vertices with $\alpha (G)\le C\sqrt{n}\log <!--FUNCTION\; APPLICATION-->n$.

Set $k=C\sqrt{n}\log <!--FUNCTION\; APPLICATION-->n$, and sample $G\sim G(n,p)$ where $p=\frac{\gamma }{\sqrt{n}}$, with $\gamma >0$ is chosen later.

Define the events:

• For each $T\in {[n]}^{(3)}$, define

  $$A_T=\text{“}{T}^{(2)}\subset G\text{”}.$$

• For each $I\in {[n]}^{(k)}$, define

  $$B_I=\text{“}{I}^{(k)}\text{independent<!--tex4ht:ref: gls@ind -->}\text{ in }G\text{”}.$$

Define the dependency graph $G$:

• $A_T\sim A_S$ for $S,T\in {[n]}^{(3)}$ if $S^{(2)}\cap T^{(2)}\ne \varnothing$.

• $A_T\sim B_I$ for $T\in {[n]}^{(3)},I\in {[n]}^{(k)}$ if $S^{(2)}\cap I^{(2)}\ne \varnothing$.

• $B_I\sim B_J$ for $I,J\in {[n]}^{(k)}$ if $I^{(2)}\cap J^{(2)}\ne \varnothing$.

Now note:

• The event $A_T$ is $\sim$ to $\le 3n$ $A_S$, $S\in {[n]}^{(3)}$.

• The event $A_T$ is $\sim$ to $\le 3n^{k-2}$ $B_I$, $I\in {[n]}^{(k)}$.

• The event $B_I$ is $\sim$ to $\le k^{2}n$ $A_S$, $S\in {[n]}^{(3)}$.

• The event $B_I$ is $\sim$ to $\le k^2{n}^{k-2}$ $B_J$, $J\in {[n]}^{(k)}$.

We choose $x_T=2p^3$ for all $T\in {[n]}^{(3)}$ (“we want to make it a bit bigger than the probability of it occuring so that we can afford the product stuff”) and $x_I=n^{-10k}$ for all $I\in {[n]}^{(k)}$.

Then

$$\begin{array}{llll}\hfill x_T\prod _{\begin{array}{c}S\in {[n]}^{(3)}\\ T\sim S\end{array}}(1-x_S)\prod _{\begin{array}{c}I\in {[n]}^{(k)}\\ I\sim T\end{array}}(1-x_I)& \ge 2p^3{(1-2p^3)}^{3n}{(1-n^{-10k})}^{3n^{k-2}}& \hfill & \\ \hfill & \ge 2p^3\exp <!--FUNCTION\; APPLICATION-->(-(1+o(1))[2p^3(3n)+3n^{-10k}{n}^{k-2}])& \hfill & \\ \hfill & =2p^3(1+o(1))& \hfill & \\ \hfill & \ge p^3& \hfill & \end{array}$$

for large enough $n$. We have $\mathbb{P}(B_I)={(1-p)}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}\le e^{-p\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$, so

$$\begin{array}{llll}\hfill x_I{(1-2p^3)}^{k^{2}n}{(1-n^{-10k})}^{k^2{n}^{k-2}}& \ge n^{-10k}\exp <!--FUNCTION\; APPLICATION-->(-(1+o(1))[2p^3{k}^{2}n+n^{-10k}{k}^2{n}^{k-2}])& \hfill & \\ \hfill & =n^{-10k}\exp <!--FUNCTION\; APPLICATION-->(-(1+o(1))(2{\gamma }^2)p{k}^2)& \hfill & \end{array}$$

Note

First choose $\gamma$ small so $e^{-2{\gamma }^{2}pk}\gg e^{-p\left(\genfrac{}{}{0ex}{}{k}{2}\right)\frac{1}{2}}$, and then choose $C\gg \frac{1}{\gamma }$, then done. □