Suppose that $\Pi$ is a balanced $r$-partition of $\llbracket{n}\rrbracket$
and that $M$ is a matching with $m$ edges such that $V(M)\subseteq P$ for some
$P\in\Pi$. If $r^{2}\cdot 2^{r+3}\leqslant n$, then

$\left|\big{\\{}G\subseteq K_{\Pi}:G\cup M\nsupseteq
K_{r+1}\big{\\}}\right|\leqslant 2^{e(K_{\Pi})-\frac{mn}{2^{10}r^{4}}}.$

###### Proof.

Let $G$ be a uniformly chosen random subgraph of $K_{\Pi}$, so that the
assertion of the lemma becomes equivalent to the inequality $\Pr(G\cup
M\nsupseteq K_{r+1})\leqslant 2^{-\frac{mn}{2^{10}r^{4}}}$. Let
$N=\prod_{Q\in\Pi\setminus\\{P\\}}|Q|$ and note that the assumption that $\Pi$
is balanced implies that $N\geqslant\left(\frac{n}{2r}\right)^{r-1}$. Denote
by $K_{r+1}^{-}$ the graph obtained from $K_{r+1}$ by removing from it a
single edge and let $\mathcal{K}$ be the collection of all copies of
$K_{r+1}^{-}$ in $K_{\Pi}$ that form a $K_{r+1}$ with an edge of $M$. Note
that $|\mathcal{K}|=mN$ and that $\Pr(G\cup M\nsupseteq
K_{r+1})=\Pr(K\nsubseteq G\text{ for all }K\in\mathcal{K})$. We may thus bound
this probability from above using Janson’s inequality. Define, as in the
statement of Theorem 5.2,

$\mu=\sum_{K\in\mathcal{K}}\left(\frac{1}{2}\right)^{e(K)}\qquad\text{and}\qquad\Delta=\sum_{\begin{subarray}{c}\\{K,K^{\prime}\\}\in\binom{\mathcal{K}}{2}\\\
E(K)\cap
E(K^{\prime})\neq\emptyset\end{subarray}}\left(\frac{1}{2}\right)^{e(K\cup
K^{\prime})}.$

Observe that the function
$\\{2,\dotsc,r\\}\ni\ell\mapsto\left(\frac{n}{2r}\right)^{\ell-1}\cdot
2^{-\binom{\ell+1}{2}}$ is increasing. Indeed, our assumption on $r$ implies
that, for each $\ell\leqslant r-1$, we have $\frac{n}{2r}\cdot
2^{\binom{\ell}{2}-\binom{\ell+1}{2}}\geqslant\frac{n}{2r}\cdot
2^{-r}\geqslant 1$. It follows that

$\frac{\mu}{2}=\frac{mN}{2}\cdot\left(\frac{1}{2}\right)^{\binom{r+1}{2}-1}\geqslant
m\cdot\left(\frac{n}{2r}\right)^{r-1}\cdot\left(\frac{1}{2}\right)^{\binom{r+1}{2}}\geqslant\frac{mn}{16r}.$

We now estimate $\Delta$. To this end, fix some $K\in\mathcal{K}$ and observe
that:

  1. (a)

For each $k\in\\{1,\dotsc,r-2\\}$, there are at most $\binom{r-1}{k}\cdot
N\cdot\left(\frac{n}{2r}\right)^{-k}$ many $K^{\prime}\in\mathcal{K}$ that
share with $K$ the two vertices in $P$ and exactly $k$ other vertices; we have
$e(K\cup K^{\prime})=2\binom{r+1}{2}-\binom{k+2}{2}-1$ for each such
$K^{\prime}$.

  2. (b)

For each $k\in\\{2,\dotsc,r-1\\}$, there are at most
$m\cdot\binom{r-1}{k}\cdot N\cdot\left(\frac{n}{2r}\right)^{-k}$ many
$K^{\prime}\in\mathcal{K}$ that share with $K$ only some $k$ vertices outside
of $P$; we have $e(K\cup K^{\prime})=2\binom{r+1}{2}-\binom{k}{2}-2$ for each
such $K^{\prime}$.

We conclude that

$\begin{split}\frac{2\Delta}{\mu^{2}}&\leqslant\frac{1}{m}\cdot\sum_{k=1}^{r-2}\binom{r-1}{k}\cdot\left(\frac{n}{2r}\right)^{-k}\cdot
2^{\binom{k+2}{2}-1}+\sum_{k=2}^{r-1}\binom{r-1}{k}\cdot\left(\frac{n}{2r}\right)^{-k}\cdot
2^{\binom{k}{2}}\\\
&\leqslant\frac{1}{m}\cdot\sum_{k=1}^{r-2}\frac{(2r^{2})^{k}\cdot
2^{\binom{k+2}{2}-1}}{n^{k}}+\sum_{k=2}^{r-1}\frac{(2r^{2})^{k}\cdot
2^{\binom{k}{2}}}{n^{k}}\\\
&\leqslant\frac{8r^{2}}{mn}+\sum_{k=2}^{r}\frac{(2r^{2})^{k}\cdot
2^{\binom{k+2}{2}}}{n^{k}}.\end{split}$

Our assumption on $r$ implies that, for every $k\in\\{2,\dotsc,r-1\\}$,

$\frac{(2r^{2})^{k+1}2^{\binom{k+3}{2}}}{n^{k+1}}=\frac{r^{2}2^{k+3}}{n}\cdot\frac{(2r^{2})^{k}2^{\binom{k+2}{2}}}{n^{k}}\leqslant\frac{1}{2}\cdot\frac{(2r^{2})^{k}2^{\binom{k+2}{2}}}{n^{k}}$

and hence, as $m\leqslant n/2$ and $r\geqslant 2$,

$\frac{2\Delta}{\mu^{2}}\leqslant\frac{8r^{2}}{mn}+2\cdot\frac{4r^{4}\cdot
2^{6}}{n^{2}}\leqslant\frac{258r^{4}}{mn}.$

We conclude that

$\Pr(G\cup M\nsubseteq
K_{r+1})\leqslant\exp\left(-\min\left\\{\frac{\mu}{2},\frac{\mu^{2}}{4\Delta}\right\\}\right)\leqslant\exp\left(-\frac{mn}{2^{10}r^{4}}\right),$

as claimed. ∎

###  6.7. Proof of Theorem 1.2

Suppose that positive integers $n$ and $r$ satisfy $2\leqslant r\leqslant\log
n/(120\log\log n)$ and let $\mathrm{Col}_{r}(n)$ and $\mathcal{F}$ denote the
families of all $r$-partite and all $K_{r+1}$-free subgraphs of $K_{n}$,
respectively. Since $\mathrm{Col}_{r}(n)\subseteq\mathcal{F}$, it suffices to
show that

$|\mathcal{F}\setminus\mathrm{Col}_{r}(n)|\leqslant
2^{-\frac{n}{(10r)^{4}}}\cdot|\mathrm{Col}_{r}(n)|.$ (30)

Let $\delta=(8\log n)^{-13}$ and let $\mathcal{P}$ be the family of all
$r$-partitions of $\llbracket{n}\rrbracket$. Define, for every graph
$G\in\mathcal{F}$,

$t(G)=\min\\{e(G\setminus K_{\Pi}):\Pi\in\mathcal{P}\\}$

and let

$\mathcal{F}_{\mathrm{close}}=\\{G\in\mathcal{F}:1\leqslant
t(G)\leqslant\delta
n^{2}\\}\qquad\text{and}\qquad\mathcal{F}_{\mathrm{far}}=\\{G\in\mathcal{F}:t(G)>\delta
n^{2}\\},$

so that
$\mathcal{F}_{\mathrm{close}}\cup\mathcal{F}_{\mathrm{far}}=\mathcal{F}\setminus\mathrm{Col}_{r}(n)$.
Furthermore, for every $G\in\mathcal{F}_{\mathrm{close}}$, let $\Pi(G)$ be an
arbitrary $r$-partition that achieves the minimum in the definition of $t(G)$.
Let $\mathcal{F}_{\mathrm{close}}^{b}$ comprise these $G$ in
$\mathcal{F}_{\mathrm{close}}$ for which $\Pi(G)$ is a balanced partition and
let
$\mathcal{F}_{\mathrm{close}}^{u}=\mathcal{F}_{\mathrm{close}}\setminus\mathcal{F}_{\mathrm{close}}^{b}$.
Finally, for every balanced partition $\Pi\in\mathcal{P}$ and every integer
$t$ satisfying $1\leqslant t\leqslant\delta n^{2}$, define

$\mathcal{F}_{t,\Pi}=\\{G\in\mathcal{F}_{\mathrm{close}}^{b}:t(G)=t\text{ and
}\Pi(G)=\Pi\\}.$

Letting $\mathcal{P}_{b}$ denote the set of balanced $r$-partitions of
$\llbracket{n}\rrbracket$, we thus have

$|\mathcal{F}\setminus\mathrm{Col}_{r}(n)|\leqslant|\mathcal{F}_{\mathrm{far}}|+|\mathcal{F}_{\mathrm{close}}^{u}|+\sum_{\Pi\in\mathcal{P}_{b}}\sum_{t=1}^{\delta
n^{2}}|\mathcal{F}_{t,\Pi}|.$ (31)

It follows from Theorem 6.2 and Lemma 6.5 that the first and the second terms
in the right-hand side of (31) are at most $2^{\mathrm{ex}(n,K_{r+1})-n}$
each. To bound the final term, we shall derive the following estimate.

######  Claim 6.10.

For every integer $t$ satisfying $1\leqslant t\leqslant\delta n^{2}$ and each
$\Pi\in\mathcal{P}_{b}$,

$|\mathcal{F}_{t,\Pi}|\leqslant 2^{e(K_{\Pi})-\frac{n}{(8r)^{4}}-t}.$

Let us first argue that inequality (31) and Claim 6.10 imply (30). Indeed,
assuming Claim 6.10, we have

$\begin{split}|\mathcal{F}\setminus\mathrm{Col}_{r}(n)|&\leqslant 2\cdot
2^{\mathrm{ex}(n,K_{r+1})-n}+\sum_{\Pi\in\mathcal{P}_{b}}\sum_{t=1}^{\delta
n^{2}}2^{e(K_{\Pi})-\frac{n}{(8r)^{4}}-t}\\\ &\leqslant
2^{\mathrm{ex}(n,K_{r+1})-n+1}+2^{-\frac{n}{(8r)^{r}}}\cdot\sum_{\Pi\in\mathcal{P}}2^{e(K_{\Pi})}.\end{split}$

Finally, since $|\mathrm{Col}_{r}(n)|\geqslant 2^{\mathrm{ex}(n,K_{r+1})}$ and
$\sum_{\Pi\in\mathcal{P}}2^{e(K_{\Pi})}\leqslant 2|\mathrm{Col}_{r}(n)|$, by
Lemma 6.6, we conclude that

$|\mathcal{F}\setminus\mathrm{Col}_{r}(n)|\leqslant\left(2^{-n+1}+2^{-\frac{n}{(8r)^{4}}+1}\right)\cdot|\mathrm{Col}_{r}(n)|,$

which yields (30). It thus suffices to prove Claim 6.10.

###### Proof of Claim 6.10.

Let $D=\left\lfloor\frac{n}{2^{14}r^{4}\log n}\right\rfloor$ and define

$\displaystyle\mathcal{F}_{t,\Pi}^{S}$
$\displaystyle=\big{\\{}G\in\mathcal{F}_{t,\Pi}:G[P]\supseteq K_{1,D}\text{
for some }P\in\Pi\big{\\}},$ $\displaystyle\mathcal{F}_{t,\Pi}^{M}$
$\displaystyle=\big{\\{}G\in\mathcal{F}_{t,\Pi}:G[P]\text{ has a matching of
size $\lceil t/(Dr)\rceil$ for some $P\in\Pi$}\big{\\}}.$

Since every graph with $t$ edges contains either a vertex with degree at least
$D$ or a matching with at least $t/D$ edges, we have
$\mathcal{F}_{t,\Pi}=\mathcal{F}_{t,\Pi}^{S}\cup\mathcal{F}_{t,\Pi}^{M}$ and
we may bound $|\mathcal{F}_{t,\Pi}|$ from above in two steps.

First, we claim that if $G\in\mathcal{F}_{t,\Pi}^{S}$ and $v\in P\in\Pi$ is
the centre vertex of a copy of $K_{1,D}$ in $G[P]$, then
$\deg_{G}(v,Q)\geqslant D$ for all $Q\in\Pi$. Indeed, if this were not true,
then moving $v$ from $P$ to $Q$ would yield a partition $\Pi^{\prime}$ such
that

$e(G\setminus K_{\Pi^{\prime}})=e(G\setminus
K_{\Pi})+\deg_{G}(v,Q)-\deg_{G}(v,P)<e(G\setminus K_{\Pi}),$

which would contradict our assumption that $\Pi=\Pi(G)$. It thus follows from
Lemma 6.8 (which we may apply as $D\geqslant n^{1/2}\geqslant 2^{r}r$ when $n$
is sufficiently large) that

$|\mathcal{F}_{t,\Pi}^{S}|\leqslant\left(n^{2}\right)^{t}\cdot
2^{e(K_{\Pi})-\frac{D^{2}}{8r^{2}}}\leqslant
2^{e(K_{\Pi})-\frac{D^{2}}{8r^{2}}+4t\log n}\leqslant 2^{e(K_{\Pi})-n-t},$

where the last inequality holds because, by our choice of $\delta$ and $D$,

$\frac{D^{2}}{8r^{2}}\geqslant\frac{n^{2}}{2^{32}r^{10}(\log
n)^{2}}\geqslant\frac{n^{2}}{(8\log n)^{12}}\geqslant 8\delta n^{2}\log
n\geqslant 4t\log n+n+t.$

Second, it follows from Lemma 6.9 that

$|\mathcal{F}_{t,\Pi}^{M}|\leqslant\left(n^{2}\right)^{t}\cdot
2^{e(K_{\Pi})-\frac{\lceil t/(Dr)\rceil n}{2^{10}r^{4}}}\leqslant
2^{e(K_{\Pi})-\frac{\lceil t/(Dr)\rceil n}{2^{10}r^{4}}+4t\log n}\leqslant
2^{e(K_{\Pi})-\frac{n}{2^{11}r^{4}}-t},$

where the last inequality holds because

$\frac{\lceil t/(Dr)\rceil n}{2^{10}r^{4}}-4t\log
n-t\geqslant\min_{\tau\in\\{1,2,\dotsc\\}}\left\\{\frac{\tau
n}{2^{10}r^{4}}-\tau Dr\cdot(4\log
n+1)\right\\}\geqslant\frac{n}{2^{11}r^{4}},$

as the definition of $D$ assures that $n\geqslant 2^{14}Dr^{4}\log n$. Since
$|\mathcal{F}_{t,\Pi}|\leqslant|\mathcal{F}_{t,\Pi}^{S}|+|\mathcal{F}_{t,\Pi}^{M}|$,
combining the two bounds above gives the assertion of the claim. ∎

##  7\. Lower bounds for $\varepsilon$-nets

###  7.1. Outline

Our (randomised) construction of planar point sets $X$ without a small
$\varepsilon$-net for the range space of lines on $X$ is a slight
simplification of the construction of Balogh and Solymosi [9]. The high-level
idea of both constructions, which can be traced back to the work of Alon [1],
may be summarised as follows. We find an integer $s$, a finite set
$X\subseteq\mathbb{R}^{2}$, and a sub-collection $\mathcal{L}$ of all lines in
$\mathbb{R}^{2}$ such that:

  1. (i)

Every line in $\mathcal{L}$ contains at most $s$ points from $X$.

  2. (ii)

The $s$-uniform hypergraph $\mathcal{H}$ whose edges are all intersections of
the lines in $\mathcal{L}$ with $X$ that have exactly $s$ points has no
independent sets larger than $(1-c)|X|$, for some constant $c>0$.

Given such $s$, $X$, and $\mathcal{L}$, we set $\varepsilon=s/|X|$ and observe
that, by (i), the complement of every $\varepsilon$-net $N$ for the range
space of lines on $X$ is an independent set of $\mathcal{H}$. By (ii), this
means that $|N|\geqslant c|X|=cs/\varepsilon$, which improves upon the trivial
bound $|N|\geqslant\Omega(1/\varepsilon)$ if $s$ can be made arbitrarily
large. The challenge is to make $s$ as large as possible, as a function of
$|X|$.

In the construction of Alon [1], the set $X$ is a generic projection of the
$d$-dimensional grid $\llbracket{s}\rrbracket^{d}$ to $\mathbb{R}^{2}$ and
$\mathcal{L}$ is the image of all combinatorial lines in
$\llbracket{s}\rrbracket^{d}$ via this projection; property (i) holds
trivially whereas property (ii), for large enough $d$, is guaranteed by the
density version of the Hales–Jewett theorem proved by Furstenberg and
Katznelson [24]. In Balogh and Solymosi’s [9] construction, $X$ was a generic
projection of a random subset of a larger, high-dimensional integer grid,
trimmed appropriately to guarantee property (i) for a careful choice of
$\mathcal{L}$; property (ii) was established with the use of the hypergraph
container theorem of Saxton and Thomason [42]. Here, we take $X$ to be a
random subset of $\llbracket{n}\rrbracket^{2}$, trimmed appropriately, and
establish (ii) using our efficient container lemma, Theorem 1.6.

###  7.2. Proof of Theorem 1.3

Let $s$ be a positive integer, let $m=10s$, and let $M$ be a prime number
satisfying $m^{m^{2}-1}\leqslant M\leqslant 2m^{m^{2}-1}$. Set $n=mM$, so that

$n\geqslant m^{m^{2}}\qquad\text{and}\qquad m\geqslant\sqrt{\frac{\log
n}{\log\log n}}.$ (32)

We shall find an $\varepsilon\in(0,1/n)$ and a set $X\subseteq\mathbb{R}^{2}$
without a small $\varepsilon$-net among the subsets of the integer grid
$\llbracket{n}\rrbracket^{2}$, which we shall from now on denote by $P$. We
will be able to prove the claimed lower bound on the smallest size of an
$\varepsilon$-net of $X$ for the range space of all lines in $\mathbb{R}^{2}$
by considering only a fairly small family $\mathcal{L}$ of lines that we now
specify.

Given an integer $h\in\llbracket{M-1}\rrbracket$ and a point
$(x_{0},y_{0})\in\llbracket{n}\rrbracket\times\llbracket{M}\rrbracket$, we let
$\ell(x_{0},y_{0};h)$ be the line passing through $(x_{0},y_{0})$ whose slope
is $M/h$, that is,

$\ell(x_{0},y_{0};h)=\big{\\{}(x_{0},y_{0})+t\cdot(h,M):t\in\mathbb{R}\big{\\}}.$

Since $M$ is prime, and thus co-prime with $h$, the vector $t\cdot(h,M)$ has
integer coordinates if and only if $t\in\mathbb{Z}$. Moreover, if $t$ is an
integer, then $y_{0}+tM\in\llbracket{n}\rrbracket$ if and only if
$t\in\\{0,\dotsc,m-1\\}$. In particular, $\ell(x_{0},y_{0};h)$ intersects $P$
in at most $m$ points; it intersects $P$ in exactly $m$ points if and only if
$x_{0}+(m-1)h\leqslant n$. Now, for every $h\in\llbracket{M-1}\rrbracket$, let

$\mathcal{L}_{h}=\big{\\{}\ell(x_{0},y_{0};h):(x_{0},y_{0})\in\llbracket{n}\rrbracket\times\llbracket{M}\rrbracket\text{
and }x_{0}+(m-1)h\leqslant n\big{\\}},$

so that every line in $\mathcal{L}_{h}$ intersects $P$ in exactly $m$ points.
Since the lines in $\mathcal{L}_{h}$ are pairwise disjoint (as they are
parallel), we have

$\left|\bigcup\mathcal{L}_{h}\right|=m\cdot|\mathcal{L}_{h}|=m\cdot\big{(}n-(m-1)h\big{)}\cdot
M=n^{2}\cdot\left(1-\frac{(m-1)h}{n}\right).$

Let $h_{\max}=\lfloor n/(10m)\rfloor$ so that $\bigcup\mathcal{L}_{h}$ has at
least $9n^{2}/10$ points for every $h\in\llbracket{h_{\max}}\rrbracket$.
Finally, define

$\mathcal{L}=\bigcup_{h=1}^{h_{\max}}\mathcal{L}_{h}$

and note that

$\frac{n^{3}}{12m^{2}}\leqslant\frac{9n^{2}}{10m}\cdot
h_{\max}\leqslant|\mathcal{L}|\leqslant\frac{n^{2}}{m}\cdot
h_{\max}\leqslant\frac{n^{3}}{10m^{2}}.$ (33)

We shall say that a set $A\subseteq P$ is _$\mathcal{L}$ -collinear_ if $A$ is
contained in some line in $\mathcal{L}$. As every line in $\mathcal{L}$
contains exactly $m$ points of $P$, the number of $a$-element
$\mathcal{L}$-collinear subsets of $P$ is precisely
$|\mathcal{L}|\cdot\binom{m}{a}$ for every $a\in\\{2,\dotsc,m\\}$.

Suppose that $p$ satisfies

$K\cdot m^{10}\cdot n^{-1/(s-1)}\cdot\log n\leqslant p\leqslant m^{-1}\cdot
n^{-1/s}$ (34)

for some large absolute constant $K$; such a number does indeed exist as

$n^{1/(s-1)-1/s}\geqslant n^{1/s^{2}}\geqslant
m^{m^{2}/s^{2}}=m^{100}\geqslant K\cdot m^{10}\cdot\log n,$

provided that $m$ is sufficiently large. Let $R$ be a $p$-random subset of $P$
and let $X\subseteq R$ be a largest subset of $R$ that contains no
$\mathcal{L}$-collinear subset of $s+1$ points. By maximality of $X$, every
point of $R\setminus X$ forms an $\mathcal{L}$-collinear $(s+1)$-element set
with some $s$ points of $X$. In particular, $|R\setminus X|$ is at most the
number of $\mathcal{L}$-collinear $(s+1)$-element subsets of $R$. It follows
that

$\mathbb{E}\big{[}|R\setminus
X|\big{]}\leqslant|\mathcal{L}|\cdot\binom{m}{s+1}\cdot
p^{s+1}\leqslant\frac{n^{3}}{10m^{2}}\cdot m^{s+1}\cdot
p^{s+1}\leqslant\frac{n^{2}p}{10m},$

by the second inequality in (34), and consequently, by Markov’s inequality,

$\Pr\big{(}|R\setminus X|\geqslant
n^{2}p/10\big{)}\leqslant\frac{\mathbb{E}\big{[}|R\setminus
X|\big{]}}{n^{2}p/10}\leqslant\frac{1}{m}\leqslant\frac{1}{10}.$

On the other hand, standard estimates for lower tails of binomial
distributions (Lemma 5.1) yield

$\Pr\big{(}|R|\leqslant
9n^{2}p/10\big{)}\leqslant\exp\left(-n^{2}p/200\right)\leqslant\exp(-n/200).$

It follows that

$\Pr\big{(}|X|\geqslant 4n^{2}p/5\big{)}\geqslant 4/5,$

provided that $n$ is sufficiently large.

######  Claim 7.1.

With probability at least $1/2$, every set $I\subseteq R$ with $|I|\geqslant
3n^{2}p/5$ contains an $\mathcal{L}$-collinear subset of $s$ points.

Together with the above calculations, Claim 7.1 implies that there exists a
set $X\subseteq P$ of at least $4n^{2}p/5$ points that has the following two
properties:

  1. (a)

$X$ has no $\mathcal{L}$-collinear subset with $s+1$ elements;

  2. (b)

every set of $3n^{2}p/5$ elements of $X$ contains an $\mathcal{L}$-collinear
$s$-element subset.

Suppose that $X$ is such a set, let $\varepsilon=s/|X|$, and assume that
$N\subseteq X$ is an $\varepsilon$-net for the range space of lines. In
particular, $N$ intersects every $\mathcal{L}$-collinear subset of $X$ that
has at least $s=\varepsilon|X|$ elements. Since $X$ contains no
$\mathcal{L}$-collinear set with more than $s$ points, $X\setminus N$ contains
no $\mathcal{L}$-collinear subset of $s$ points, and thus

$|N|=|X|-|X\setminus N|>|X|-3n^{2}p/5\geqslant|X|/4=s/(4\varepsilon).$

Finally, since $1/\varepsilon=|X|/s\leqslant|P|=n^{2}$, we have, using (32),

$\frac{s}{4}=\frac{m}{40}\geqslant\frac{1}{40}\cdot\sqrt{\frac{\log
n}{\log\log
n}}\geqslant\frac{1}{80}\cdot\sqrt{\frac{\log(1/\varepsilon)}{\log\log(1/\varepsilon)}}.$

This gives the assertion of the theorem.

We now prove Claim 7.1. Let $\mathcal{H}$ be the $s$-uniform hypergraph with
vertex set $P$ whose edges are all $\mathcal{L}$-collinear $s$-element subsets
of $P$. The assertion of the claim is that, with probability at least $1/2$,
the random set $R$ contains no independent set of $\mathcal{H}$ that has at
least $3n^{2}p/5$ elements. This is a simple consequence of the following
lemma, which lies at the heart of the matter.

######  Lemma 7.2.

There is a family $\mathcal{C}$ of at most $\exp(pn^{2}/300)$ containers for
the independent sets of $\mathcal{H}$ such that $|C|\leqslant n^{2}/2$ for
every $C\in\mathcal{C}$.

We first show how Lemma 7.2 implies the assertion of Claim 7.1. Let
$\mathcal{C}$ be a family of containers for the independent sets of
$\mathcal{H}$ supplied by the lemma and let $\mathcal{B}$ be the event that
$R$ contains an independent set of $\mathcal{H}$ with at least $3n^{2}p/5$
elements. Since every independent set of $\mathcal{H}$ is contained in some
member of $\mathcal{C}$, each of which has at most $n^{2}/2$ elements, we have

$\Pr(\mathcal{B})\leqslant\sum_{C\in\mathcal{C}}\Pr\left(|R\cap C|\geqslant
3n^{2}p/5\right)\leqslant|\mathcal{C}|\cdot\Pr\left(\mathrm{Bin}(n^{2}/2,p)\geqslant
3n^{2}p/5\right).$

Standard estimates for upper tails of binomial distributions (Lemma 5.1) yield

$\Pr\left(\mathrm{Bin}(n^{2}/2,p)\geqslant
3n^{2}p/5\right)\leqslant\exp\left(-n^{2}p/150\right)$

and, consequently,

$\Pr(\mathcal{B})\leqslant|\mathcal{C}|\cdot\exp\left(-n^{2}p/150\right)\leqslant\exp\left(-n^{2}p/300\right)\leqslant\exp(-n/300)\leqslant
1/2,$

provided that $n$ is sufficiently large.

Finally, we prove Lemma 7.2 by combining our ‘packaged’ hypergraph container
lemma, Theorem 1.6, with the following supersaturation statement for the
hypergraph $\mathcal{H}$ of $\mathcal{L}$-collinear $s$-tuples.

######  Lemma 7.3.

If $Q\subseteq P$ has at least $n^{2}/3$ points, then
$e\big{(}\mathcal{H}[Q]\big{)}\geqslant|\mathcal{L}|$.

###### Proof.

Define $b_{s}\colon\mathbb{R}\to\mathbb{R}$ by

$b_{s}(x)=\begin{cases}\binom{x}{s}&\text{if $x\geqslant s-1$,}\\\ 0&\text{if
$x\leqslant s-1$,}\end{cases}$

so that $b_{s}$ is convex and $b_{s}(a)=\binom{a}{s}$ whenever $a$ is a
nonnegative integer. Jensen’s inequality gives

$e\big{(}\mathcal{H}[Q]\big{)}=\sum_{\ell\in\mathcal{L}}\binom{|\ell\cap
Q|}{s}=\sum_{\ell\in\mathcal{L}}b_{s}\big{(}|\ell\cap
Q|\big{)}\geqslant|\mathcal{L}|\cdot
b_{s}\left(\frac{1}{|\mathcal{L}|}\cdot\sum_{\ell\in\mathcal{L}}|\ell\cap
Q|\right).$

Recall that, for every $h\in\llbracket{h_{\max}}\rrbracket$, the lines in
$\mathcal{L}_{h}$ cover all but at most $n^{2}/10$ points of $P$. In
particular, for every such $h$,

$\sum_{\ell\in\mathcal{L}_{h}}|\ell\cap
Q|\geqslant|Q|-\frac{n^{2}}{10}\geqslant\frac{n^{2}}{5}$

and thus

$\frac{1}{|\mathcal{L}|}\cdot\sum_{\ell\in\mathcal{L}}|\ell\cap
Q|=\frac{1}{|\mathcal{L}|}\cdot\sum_{h=1}^{h_{\max}}\sum_{\ell\in\mathcal{L}_{h}}|\ell\cap
Q|\geqslant\frac{h_{\max}}{|\mathcal{L}|}\cdot\frac{n^{2}}{5}\geqslant\frac{m}{5}.$

Consequently,

$e\big{(}\mathcal{H}[Q]\big{)}\geqslant|\mathcal{L}|\cdot
b_{s}\big{(}m/5\big{)}=|\mathcal{L}|\cdot\binom{m/5}{s}\geqslant|\mathcal{L}|,$

as claimed. ∎

###### Proof of Lemma 7.2.

Set

$q=\frac{p}{300m^{5}\log n}\qquad\text{and}\qquad E=|\mathcal{L}|.$

We now verify that we may apply Theorem 1.6, with $\alpha\leftarrow 1/2$ and
$\beta\leftarrow 1/3$, to the hypergraph $\mathcal{H}$. First, we have

$\alpha\beta q\cdot v(\mathcal{H})=\frac{pn^{2}}{1800m^{5}\log n}\geqslant
10^{9}s^{7}\qquad\text{and}\qquad 10^{4}s^{5}q=\frac{10^{4}s^{5}p}{m^{6}\log
n}\leqslant\frac{1}{\log n}\leqslant\beta,$

provided that $n$ is sufficiently large. Second, for every
$t\in\\{2,\dotsc,s\\}$, by (33) and (34),

$\left(\frac{q}{10^{6}s^{5}}\right)^{t-1}\cdot\frac{E}{v(\mathcal{H})}=\left(\frac{p}{3\cdot
10^{8}s^{5}m^{5}\log
n}\right)^{t-1}\cdot\frac{|\mathcal{L}|}{n^{2}}\geqslant\left(\frac{K\cdot
m^{5}\cdot n^{-1/(s-1)}}{10^{8}s^{5}}\right)^{s-1}\cdot\frac{n}{12m^{2}}\\\
=\left(\frac{K}{10^{3}}\right)^{s-1}\cdot\frac{1}{12m^{2}}\geqslant
2^{m}\geqslant\binom{m-t}{s-t}=\Delta_{t}(\mathcal{H}),$

provided that $K$ is sufficiently large. The theorem supplies a collection
$\mathcal{C}$ of containers for the independent sets of $\mathcal{H}$ such
that

$\begin{split}|\mathcal{C}|&\leqslant\exp\left(10^{4}s^{5}\beta^{-1}\log(e/\alpha)\cdot
q\log(e/q)\cdot v(\mathcal{H})\right)\\\ &\leqslant\exp\left(m^{5}\cdot q\log
n\cdot n^{2}\right)\leqslant\exp\left(pn^{2}/300\right),\end{split}$

where we used the inequality $q\geqslant e/n$, which holds if $K$ is
sufficiently large, and, for every $C\in\mathcal{C}$, either
$|C|\leqslant\alpha\cdot v(\mathcal{H})=n^{2}/2$ or there is a subset
$W\subseteq C$ with $|W|\geqslant(1-\beta)|C|=2|C|/3$ such that
$e(\mathcal{H}[W])<E=|\mathcal{L}|$. We claim that, in fact, $|C|\leqslant
n^{2}/2$ for every $C\in\mathcal{C}$. Indeed, if $|C|>n^{2}/2$ and $W\subseteq
C$ satisfies $|W|\geqslant 2|C|/3>n^{2}/3$, then
$e(\mathcal{H}[W])\geqslant|\mathcal{L}|$, by Lemma 7.3. ∎

##  8\. Upper bounds on Ramsey numbers

In this section, we derive the upper bounds on Folkman numbers and on induced
Ramsey numbers stated in Theorems 1.4 and 1.5. We shall do this by building
containers for non-Ramsey colourings of subgraphs of a large complete graph
$K_{N}$ and examining how a random subgraph of $K_{N}$, drawn with an
appropriately chosen distribution for each of the two theorems, intersects
these containers. This approach to studying Ramsey properties of random graphs
was introduced in the work of Nenadov and Steger [34]. The only Ramsey-
theoretic ingredient in our proof is the following supersaturated version of
Ramsey’s theorem, which is a refinement of [34, Corollary 2.2].

######  Lemma 8.1.

Suppose that $n$ and $k$ are positive integers and let $R=R(n;k)$. If
$N\geqslant R$, then every colouring $c\colon
E(K_{N})\to\llbracket{k+1}\rrbracket$ either assigns the colour $k+1$ to at
least $(1/2)\cdot(N/R)^{2}$ edges or it contains at least
$(1/2)\cdot(N/R)^{n}$ monochromatic copies of $K_{n}$ in colours $1,\dotsc,k$.

###### Proof.

The choice of $R$ guarantees that the edge-colouring induced by every subset
of $R$ vertices of $K_{N}$ contains either an edge coloured $k+1$ or a
monochromatic copy of $K_{n}$ in one of the remaining $k$ colours. On the
other hand, each edge and each copy of $K_{n}$ are contained in, respectively,
$\binom{N-2}{R-2}$ and $\binom{N-n}{R-n}$ such subsets. Denoting by $M$ the
total number of monochromatic copies of $K_{n}$ in colours $1,\dotsc,k$, we
thus have

$\binom{N}{R}\leqslant\left|c^{-1}(k+1)\right|\cdot\binom{N-2}{R-2}+M\cdot\binom{N-n}{R-n}.$
(35)

In particular, since, for every $\ell\in\\{2,n\\}$,

$\binom{N}{R}\cdot\binom{N-\ell}{R-\ell}^{-1}=\binom{N}{\ell}\cdot\binom{R}{\ell}^{-1}\geqslant\left(\frac{N}{R}\right)^{\ell}$

inequality (35) implies that either
$|c^{-1}(k+1)|\geqslant(1/2)\cdot(N/R)^{2}$ or
$M\geqslant(1/2)\cdot(N/R)^{n}$. ∎

###  8.1. Folkman numbers (proof of Theorem 1.4)

Let $k$ and $n$ be positive integers, let $R=R(n;k)$ and suppose that an
integer $N$ satisfies

$N\geqslant(\Gamma knR)^{21n^{2}}$ (36)

for some large constant $\Gamma$. We shall give a randomised construction of a
$K_{n+1}$-free subgraph of $K_{N}$ that satisfies $G\rightarrow(K_{n})_{k}$,
proving that $F(n;k)\leqslant N$. We shall from now on assume that $k\geqslant
2$ and $n\geqslant 3$, as otherwise the assertion of the theorem is trivial.

Suppose that $G\subseteq K_{N}$. We shall identify a $k$-colouring $c\colon
E(G)\to\llbracket{k}\rrbracket$ of the edges of $G$ with the set

$\big{\\{}(e,c_{e}):e\in E(G)\big{\\}}\subseteq
E(K_{N})\times\llbracket{k}\rrbracket.$

Let $\mathcal{H}$ be the hypergraph with vertex set
$E(K_{N})\times\llbracket{k}\rrbracket$ whose edges are all sets of the form

$\varphi\big{(}E(K_{n})\big{)}\times\\{i\\},$

where $\varphi\colon V(K_{n})\to V(K_{N})$ is an arbitrary injection and
$i\in\llbracket{k}\rrbracket$. If a graph $G\subseteq K_{N}$ admits a
colouring $c\colon E(G)\to\llbracket{k}\rrbracket$ with no monochromatic copy
of $K_{n}$, then $c$, when viewed as a subset of
$E(K_{N})\times\llbracket{k}\rrbracket$, is an independent set of
$\mathcal{H}$.

We shall say that a graph $G\subseteq E(K_{N})$ is _compatible_ with a set
$C\subseteq E(K_{N})\times\llbracket{k}\rrbracket$ if there exists a colouring
$c\colon E(G)\to\llbracket{k}\rrbracket$ that is contained in $C$.
Equivalently, $G$ is compatible with $C$ if and only if
$\big{(}\\{e\\}\times\llbracket{k}\rrbracket\big{)}\cap C\neq\emptyset$ for
every $e\in E(G)$. In other words, defining

$X(C)=\big{\\{}e\in E(K_{N}):\big{(}e\times\llbracket{k}\rrbracket\big{)}\cap
C=\emptyset\big{\\}},$

$G$ is compatible with $C$ if and only if $X(C)\cap E(G)=\emptyset$.

Suppose that $p$ satisfies

$D\cdot(knR)^{20}\cdot N^{-2/(n+1)}\log N\leqslant
p\leqslant\frac{N^{-2/(n+2)}}{DR}$ (37)

for some large constant $D$; such a number does indeed exist as (36) implies
that

$\frac{N^{2/(n+1)-2/(n+2)}}{\log N}\geqslant N^{1/n^{2}}\geqslant
D^{2}\cdot(knR)^{21},$

provided that $\Gamma$ is sufficiently large. The following lemma is key.

######  Lemma 8.2.

There is a family $\mathcal{C}$ of at most
$\exp\left(\frac{pN^{2}}{256R^{2}}\right)$ containers for the independent sets
of $\mathcal{H}$ such that $|X(C)|\geqslant\left(\frac{N}{4R}\right)^{2}$ for
every $C\in\mathcal{C}$.

We first show how Lemma 8.2 implies the assertion of the theorem. To this end,
suppose that $G\sim G_{N,p}$ and denote by $Z$ the number of copies of
$K_{n+1}$ in $G$. The upper bound in (37) implies that

$\mathbb{E}[Z]\leqslant
p^{\binom{n+1}{2}}N^{n+1}=pN^{2}\cdot\left(p^{(n+2)/2}N\right)^{n-1}\leqslant\frac{pN^{2}}{(DR)^{(n+2)(n-1)/2}}\leqslant\frac{pN^{2}}{64R^{2}},$

provided that $D$ is sufficiently large. Let $G^{\prime}$ be the subgraph
obtained from $G$ by deleting an arbitrary edge from every copy of $K_{n+1}$;
observe that $K_{n+1}\nsubseteq G^{\prime}$ and $e(G^{\prime})\geqslant
e(G)-Z$.

Suppose that $G^{\prime}\not\rightarrow(K_{n})_{k}$. This means that there is
a colouring $c\colon E(G^{\prime})\to\llbracket{k}\rrbracket$ that is an
independent set of $\mathcal{H}$. Therefore, $G^{\prime}$ must be compatible
with some container from $\mathcal{C}$. In other words, there is some
$C\in\mathcal{C}$ such that $X(C)\cap E(G^{\prime})=\emptyset$ and,
consequently,

$|X(C)\cap E(G)|\leqslant e(G)-e(G^{\prime})\leqslant Z.$

We may conclude that

$\Pr\big{(}G^{\prime}\not\rightarrow(K_{n})_{k}\big{)}\leqslant\Pr\big{(}Z>2\mathbb{E}[Z]\big{)}+\sum_{C\in\mathcal{C}}\Pr\big{(}|X(C)\cap
E(G)|\leqslant 2\mathbb{E}[Z]\big{)}.$ (38)

Fix an arbitrary $C\in\mathcal{C}$. Since
$|X(C)|\geqslant\frac{N^{2}}{16R^{2}}$, standard estimates on the lower tails
of binomial distributions (Lemma 5.1) yield

$\Pr\big{(}|X(C)\cap E(G)|\leqslant
2\mathbb{E}[Z]\big{)}\leqslant\Pr\left(\mathrm{Bin}\left(\frac{N^{2}}{16R^{2}},p\right)\leqslant\frac{pN^{2}}{32R^{2}}\right)\leqslant\exp\left(-\frac{pN^{2}}{128R^{2}}\right).$

Substituting this estimate and the inequality $\Pr(Z>2\mathbb{E}[Z])<1/2$ into
(38) yields

$\Pr\big{(}G^{\prime}\not\rightarrow(K_{n})_{k}\big{)}\leqslant\frac{1}{2}+\exp\left(-\frac{pN^{2}}{256R^{2}}\right)\leqslant\frac{1}{2}+e^{-N}\leqslant\frac{3}{4}.$

In particular, there is a graph $G^{\prime}\subseteq K_{N}$ such that
$G^{\prime}\nsupseteq K_{n+1}$ and $G^{\prime}\rightarrow(K_{n})_{k}$, as
claimed.

###### Proof of Lemma 8.2.

Set

$s=\binom{n}{2},\qquad q=\frac{p}{(10knR)^{10}\log
N},\qquad\beta=\frac{1}{16kR^{2}},\qquad\text{and}\qquad
E=\left(\frac{N}{2R}\right)^{n}.$

We now verify that we may apply Theorem 1.6, with
$\alpha\leftarrow\frac{1}{2k}$, to the hypergraph $\mathcal{H}$. First, as
$s\leqslant n^{2}$, we have, by (36) and (37),

$\alpha\beta q\cdot v(\mathcal{H})\geqslant\frac{D\cdot(knR)^{10}\cdot
N^{-2/(n+2)}}{10^{10}}\cdot\binom{N}{2}\geqslant N\geqslant 2^{n/2}\geqslant
10^{9}s^{7}$

and

$10^{4}s^{5}q\leqslant 10^{4}s^{5}\cdot
N^{-2/(n+2)}\leqslant\frac{10^{4}n^{10}}{(knR)^{21n}}\leqslant\frac{1}{16kR^{2}}=\beta,$

provided that $n$ is sufficiently large. Second, suppose that
$t\in\\{2,\dotsc,s\\}$ and let $\ell\in\\{3,\dotsc,n\\}$ be the unique integer
satisfying $\binom{\ell-1}{2}<t\leqslant\binom{\ell}{2}$, so that

$t-1\leqslant\binom{\ell}{2}-1=\frac{(\ell+1)(\ell-2)}{2}\leqslant\frac{(n+1)(\ell-2)}{2}.$

Since a graph with $t$ edges must have at least $\ell$ vertices, we have

$\Delta_{t}(\mathcal{H})=k\cdot\binom{N-\ell}{n-\ell}\leqslant kN^{n-\ell}$

and, consequently,

$\displaystyle\left(\frac{q}{10^{6}s^{5}}\right)^{t-1}\cdot\frac{E}{v(\mathcal{H})}\cdot\frac{1}{\Delta_{t}(\mathcal{H})}$
$\displaystyle\geqslant\left(\frac{q}{10^{6}s^{5}}\right)^{\frac{(n+1)(\ell-2)}{2}}\cdot\frac{\big{(}N/(2R)\big{)}^{n}}{kN^{2}}\cdot\frac{1}{kN^{n-\ell}}$
$\displaystyle=\left(\frac{p}{10^{16}n^{20}(kR)^{10}\log
N}\right)^{\frac{(n+1)(\ell-2)}{2}}\cdot\frac{N^{\ell-2}}{k^{2}(2R)^{n}}$
$\displaystyle\geqslant\left(\frac{pN^{2/(n+1)}}{(10knR)^{20}\log
N}\right)^{\frac{(n+1)(\ell-2)}{2}}\geqslant 1,$

where the last inequality follows from (37). The theorem supplies a collection
$\mathcal{C}$ of containers for the independent sets of $\mathcal{H}$
satisfying

$\begin{split}|\mathcal{C}|&\leqslant\exp\left(10^{4}s^{5}\beta^{-1}\log(e/\alpha)\cdot
q\log(e/q)\cdot v(\mathcal{H})\right)\\\
&\leqslant\exp\left(10^{6}n^{10}R^{2}k\log
k\cdot\frac{p\log\left(10knR/p\right)}{10^{9}(knR)^{10}\log N}\cdot
k\binom{N}{2}\right)\leqslant\exp\left(\frac{pN^{2}}{256R^{2}}\right),\end{split}$

provided that $N$ is sufficiently large, such that, for every
$C\in\mathcal{C}$, either $|C|\leqslant\alpha\cdot v(\mathcal{H})$ or there is
a subset $W\subseteq C$ with $|W|\geqslant(1-\beta)|C|\geqslant|C|-\beta
k\binom{N}{2}$ and $e(\mathcal{H}[W])<E$.

It remains to show that $|X(C)|\geqslant\left(\frac{N}{4R}\right)^{2}$ for
every $C\in\mathcal{C}$. Suppose that this were not true. If
$|C|\leqslant\alpha
v(\mathcal{H})=\frac{k}{2k}\binom{N}{2}=\frac{1}{2}\binom{N}{2}$, then

$|X(C)|\geqslant\binom{N}{2}-|C|\geqslant\frac{1}{2}\binom{N}{2}\geqslant\left(\frac{N}{4R}\right)^{2},$

so we may assume that $|C|>\alpha v(\mathcal{H})$. In particular, there must
be a subset $W\subseteq C$ with $|C\setminus W|\leqslant\beta k\binom{N}{2}$
such that $e(\mathcal{H}[W])<E$. Observe that

$|X(W)|\leqslant|X(C)|+|C\setminus
W|\leqslant\left(\frac{N}{4R}\right)^{2}+\beta
k\binom{N}{2}\leqslant\frac{N^{2}}{8R^{2}}$ (39)

and let $c\colon E(K_{N})\to\llbracket{k+1}\rrbracket$ be an arbitrary
colouring such that $(e,c_{e})\in W$ for every $e\notin X(W)$ and $c_{e}=k+1$
otherwise. By Lemma 8.1, either
$|X(W)|=|c^{-1}(k+1)|\geqslant(1/2)\cdot(N/R)^{2}$ or the colouring $c$ has at
least $(1/2)\cdot(N/R)^{n}$ monochromatic copies of $K_{n}$ in colours
$1,\dotsc,k$. However, the former inequality contradicts (39) and thus the
latter must hold. Finally, note that, if $K$ is an arbitrary copy of $K_{n}$
in $K_{N}$ that $c$ colours with some $i\in\llbracket{k}\rrbracket$, then
$E(K)\times\\{i\\}\subseteq W$. This implies that
$e(\mathcal{H}[W])\geqslant(1/2)\cdot(N/R)^{n}\geqslant E$, contradicting our
assumption. ∎

###  8.2. Induced Ramsey numbers (proof of Theorem 1.5)

Let $k$ be a positive integer, let $H$ be an arbitrary $n$-vertex graph, let
$R=R(n;k)$, and suppose that an integer $N$ satisfies

$N\geqslant(10n^{2}kR)^{7n}.$ (40)

We shall prove that, with probability very close to one, the uniformly chosen
random subgraph of $K_{N}$ is induced-Ramsey for $H$ in $k$ colours, proving
that $R_{\mathrm{ind}}(H;k)\leqslant N$. We shall from now on assume that
$k\geqslant 2$ and $n\geqslant 3$, as otherwise the assertion of the theorem
is trivial.

Suppose that $G\subseteq K_{N}$. We shall identify a $k$-colouring $c\colon
E(G)\to\llbracket{k}\rrbracket$ of the edges of $G$ with the set

$\big{\\{}(e,c_{e}):e\in E(G)\big{\\}}\cup\big{\\{}(e,0):e\in
E(K_{N})\setminus E(G)\big{\\}}\subseteq E(K_{N})\times\\{0,\dotsc,k\\}.$

(That is, we extend $c$ to a colouring of $E(K_{N})$ by colouring all edges of
$K_{N}\setminus G$ zero.) Let $\mathcal{H}$ be the hypergraph with vertex set
$E(K_{N})\times\\{0,\dotsc,k\\}$ whose edges are all sets of the form

$\left(\varphi\big{(}E(H)\big{)}\times\\{i\\}\right)\cup\left(\varphi\big{(}E(K_{n})\setminus
E(H)\big{)}\times\\{0\\}\right),$

where $\varphi\colon V(H)\to V(K_{N})$ is an arbitrary injection and
$i\in\llbracket{k}\rrbracket$. If a graph $G\subseteq K_{N}$ admits a
colouring $c\colon E(G)\to\llbracket{k}\rrbracket$ such that $c^{-1}(i)$ does
not contain a copy of $H$ that is induced in $G$ for any
$i\in\llbracket{k}\rrbracket$, then $c$, when viewed as a subset of
$E(K_{N})\times\\{0,\dotsc,k\\}$, is an independent set of $\mathcal{H}$.

We shall say that a graph $G\subseteq E(K_{N})$ is _compatible_ with a set
$C\subseteq E(K_{N})\times\\{0,\dotsc,k\\}$ if there exists a colouring
$c\colon E(G)\to\llbracket{k}\rrbracket$ that is contained in $C$.
Equivalently, $G$ is compatible with $C$ if and only if $(e,0)\in C$ for every
$e\in E(K_{N})\setminus E(G)$ and
$\big{(}\\{e\\}\times\llbracket{k}\rrbracket\big{)}\cap C\neq\emptyset$ for
every $e\in E(G)$. In other words, defining

$\displaystyle X_{1}(C)$ $\displaystyle=\big{\\{}e\in E(K_{N}):(e,0)\notin
C\big{\\}}\quad\text{and}$ $\displaystyle X_{2}(C)$
$\displaystyle=\big{\\{}e\in
E(K_{N}):\big{(}e\times\llbracket{k}\rrbracket\big{)}\cap
C=\emptyset\big{\\}},$

$G$ is compatible with $C$ if and only if $X_{1}(C)\subseteq E(G)$ and
$X_{2}(C)\cap E(G)=\emptyset$. The following lemma is key.

######  Lemma 8.3.

There is a family $\mathcal{C}$ of at most
$\exp\left(\frac{N^{2}}{100R^{2}}\right)$ containers for the independent sets
of $\mathcal{H}$ such that $|X_{1}(C)\cup
X_{2}(C)|\geqslant\left(\frac{N}{4R}\right)^{2}$ for every $C\in\mathcal{C}$.

Assuming that Lemma 8.3 is true, suppose that $G\sim G_{N,1/2}$. If
$G\not\rightarrow_{\mathrm{ind}}(H)_{k}$, then $G$ must be compatible with
some container from $\mathcal{C}$. It follows that

$\displaystyle\Pr\big{(}G\not\rightarrow_{\mathrm{ind}}(H)_{k}\big{)}$
$\displaystyle\leqslant\sum_{C\in\mathcal{C}}\Pr\big{(}X_{1}(C)\subseteq
E(G)\text{ and }X_{2}(C)\cap E(G)=\emptyset\big{)}$
$\displaystyle\leqslant\sum_{C\in\mathcal{C}}2^{-|X_{1}(C)\cup
X_{2}(C)|}\leqslant|\mathcal{C}|\cdot 2^{-(N/(4R))^{2}}$
$\displaystyle\leqslant\exp\left(\frac{N^{2}}{100R^{2}}-\frac{N^{2}\log
2}{16R^{2}}\right)\leqslant\exp\left(-N\right).$

###### Proof of Lemma 8.3.

Set

$s=\binom{n}{2},\qquad
q=\frac{1}{(kR)^{5}},\qquad\beta=\frac{1}{16kR^{2}},\qquad\text{and}\qquad
E=\left(\frac{N}{2R}\right)^{n}.$

We now verify that we may apply Theorem 1.6, with
$\alpha\leftarrow\frac{1}{3k}$, to the hypergraph $\mathcal{H}$. First, as
$s\leqslant n^{2}$, we have

$\alpha\beta q\cdot
v(\mathcal{H})=\frac{1}{48(kR)^{7}}\cdot(k+1)\binom{N}{2}\geqslant N\geqslant
2^{n/2}\geqslant 10^{9}s^{7}$

and

$10^{4}s^{5}q=\frac{10^{4}s^{5}}{(kR)^{5}}\leqslant\frac{10^{4}n^{10}}{(kR)^{5}}\leqslant\frac{10^{4}n^{10}}{(kR)^{2}\cdot
2^{n}}\leqslant\frac{1}{16kR^{2}}=\beta,$

provided that $n$ is sufficiently large. Second, suppose that
$t\in\\{2,\dotsc,s\\}$ and let $\ell\in\\{3,\dotsc,n\\}$ be the unique integer
satisfying $\binom{\ell-1}{2}<t\leqslant\binom{\ell}{2}$, so that

$t-1\leqslant\binom{\ell}{2}-1=\frac{(\ell+1)(\ell-2)}{2}\leqslant n(\ell-2).$

Since a graph with $t$ edges must have at least $\ell$ vertices, we have

$\Delta_{t}(\mathcal{H})=k\cdot\binom{N-\ell}{n-\ell}\leqslant kN^{n-\ell}$

and, consequently,

$\displaystyle\left(\frac{q}{10^{6}s^{5}}\right)^{t-1}\cdot\frac{E}{v(\mathcal{H})}\cdot\frac{1}{\Delta_{t}(\mathcal{H})}$
$\displaystyle\geqslant\left(\frac{q}{10^{6}s^{5}}\right)^{n(\ell-2)}\cdot\frac{\big{(}N/(2R)\big{)}^{n}}{kN^{2}}\cdot\frac{1}{kN^{n-\ell}}$
$\displaystyle=\left(\frac{1}{10^{6}(skR)^{5}}\right)^{n(\ell-2)}\cdot\frac{N^{\ell-2}}{k^{2}(2R)^{n}}$
$\displaystyle\geqslant\left(\frac{N^{1/n}}{10^{7}(skR)^{6}}\right)^{n(\ell-2)}\geqslant
1,$

where the last inequality follows from (40). The theorem supplies a collection
$\mathcal{C}$ of containers for the independent sets of $\mathcal{H}$
satisfying

$\begin{split}|\mathcal{C}|&\leqslant\exp\left(10^{4}s^{5}\beta^{-1}\log(e/\alpha)\cdot
q\log(e/q)\cdot v(\mathcal{H})\right)\\\
&\leqslant\exp\left(10^{7}n^{10}R^{2}k\log
k\cdot\frac{5\log\left(ekR\right)}{(kR)^{5}}\cdot(k+1)\binom{N}{2}\right)\leqslant\exp\left(\frac{N^{2}}{100R^{2}}\right),\end{split}$

provided that $n$ is sufficiently large, such that, for every
$C\in\mathcal{C}$, either $|C|\leqslant\alpha\cdot v(\mathcal{H})$ or there is
a subset $W\subseteq C$ with
$|W|\geqslant(1-\beta)|C|\geqslant|C|-\beta(k+1)\binom{N}{2}$ and
$e(\mathcal{H}[W])<E$.

It remains to show that $|X_{1}(C)\cup
X_{2}(C)|\geqslant\left(\frac{N}{4R}\right)^{2}$ for every $C\in\mathcal{C}$.
Suppose that this were not true and set $X(C)=X_{1}(C)\cup X_{2}(C)$. If
$|C|\leqslant\alpha
v(\mathcal{H})=\frac{k+1}{3k}\binom{N}{2}\leqslant\frac{1}{2}\binom{N}{2}$,
then

$|X(C)|\geqslant\binom{N}{2}-|C|\geqslant\frac{1}{2}\binom{N}{2}\geqslant\left(\frac{N}{4R}\right)^{2},$

so we may assume that $|C|>\alpha v(\mathcal{H})$. In particular, there must
be a $W\subseteq C$ with $|C\setminus W|\leqslant\beta(k+1)\binom{N}{2}$ such
that $e(\mathcal{H}[W])<E$. Observe that

$|X(W)|\leqslant|X(C)|+|C\setminus
W|\leqslant\left(\frac{N}{4R}\right)^{2}+\beta(k+1)\binom{N}{2}\leqslant\frac{N^{2}}{8R^{2}}$
(41)

and let $c\colon E(K_{N})\to\llbracket{k+1}\rrbracket$ be an arbitrary
colouring such that $(e,c_{e})\in W$ for every $e\notin X(W)$ and $c_{e}=k+1$
otherwise. By Lemma 8.1, either
$|X(W)|=|c^{-1}(k+1)|\geqslant(1/2)\cdot(N/R)^{2}$ or the colouring $c$ has at
least $(1/2)\cdot(N/R)^{n}$ monochromatic copies of $K_{n}$ in colours
$1,\dotsc,k$. However, the former inequality contradicts (41) and thus the
latter must hold. Let $K$ be an arbitrary copy of $K_{n}$ in $K_{N}$ that $c$
colours with some $i\in\llbracket{k}\rrbracket$. Since $E(K)\cap
X_{1}(W)=\emptyset$, then $E(K)\times\\{0,i\\}\subseteq W$ and, as a result,
any injection $\varphi\colon V(H)\to V(K)$ corresponds to an edge of
$\mathcal{H}[W]$. This implies that
$e(\mathcal{H}[W])\geqslant(1/2)\cdot(N/R)^{n}\geqslant E$, contradicting our
assumption. ∎

## References

  * [1] N. Alon, _A non-linear lower bound for planar epsilon-nets_ , Discrete Comput. Geom. 47 (2012), 235–244.
  * [2] N. Alon and J. H. Spencer, _The probabilistic method_ , fourth ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016.
  * [3] B. Aronov, E. Ezra, and M. Sharir, _Small-size $\epsilon$-nets for axis-parallel rectangles and boxes_, SIAM J. Comput. 39 (2010), 3248–3282.
  * [4] J. Balogh, B. Bollobás, and M. Simonovits, _The typical structure of graphs without given excluded subgraphs_ , Random Structures Algorithms 34 (2009), 305–318.
  * [5] J. Balogh, N. Bushaw, M. Collares, H. Liu, R. Morris, and M. Sharifzadeh, _The typical structure of graphs with no large cliques_ , Combinatorica 37 (2017), 617–632.
  * [6] J. Balogh, R. Morris, and W. Samotij, _Independent sets in hypergraphs_ , J. Amer. Math. Soc. 28 (2015), 669–709.
  * [7] by same author, _The method of hypergraph containers_ , Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. 3, 2018, pp. 3045–3078.
  * [8] J. Balogh, R. Morris, W. Samotij, and L. Warnke, _The typical structure of sparse $K_{r+1}$-free graphs_, Trans. Amer. Math. Soc. 368 (2016), 6439–6485.
  * [9] J. Balogh and J. Solymosi, _On the number of points in general position in the plane_ , Discrete Anal. (2018), Paper No. 16, 20.
  * [10] A. Bernshteyn, M. Delcourt, H. Towsner, and A. Tserunyan, _A short nonalgorithmic proof of the containers theorem for hypergraphs_ , Proc. Amer. Math. Soc. 147 (2019), 1739–1749.
  * [11] B. Bollobás and V. Nikiforov, _The number of graphs with large forbidden subgraphs_ , European J. Combin. 31 (2010), 1964–1968.
  * [12] D. Conlon, D. Dellamonica, S. La Fleur, V. Rödl, and M. Schacht, _A note on induced Ramsey numbers_ , A journey through discrete mathematics, Springer, Cham, 2017, pp. 357–366.
  * [13] D. Conlon, J. Fox, and B. Sudakov, _On two problems in graph Ramsey theory_ , Combinatorica 32 (2012), 513–535.
  * [14] D. Conlon and W. T. Gowers, _Combinatorial theorems in sparse random sets_ , Ann. of Math. (2) 184 (2016), 367–454.
  * [15] W. Deuber, _Generalizations of Ramsey’s theorem_ , Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, 1975, pp. 323–332. Colloq. Math. Soc. János Bolyai, Vol. 10.
  * [16] P. Erdős, _On some problems in graph theory, combinatorial analysis and combinatorial number theory_ , Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, pp. 1–17.
  * [17] P. Erdős, P. Frankl, and V. Rödl, _The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent_ , Graphs Combin. 2 (1986), 113–121.
  * [18] P. Erdős, A. Hajnal, and L. Pósa, _Strong embeddings of graphs into colored graphs_ , Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, 1975, pp. 585–595. Colloq. Math. Soc. János Bolyai, Vol. 10.
  * [19] P. Erdős and G. Szekeres, _A combinatorial problem in geometry_ , Compositio Math. 2 (1935), 463–470.
  * [20] P. Erdős, D. J. Kleitman, and B. L. Rothschild, _Asymptotic enumeration of $K_{n}$-free graphs_, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Accad. Naz. Lincei, Rome, 1976, pp. 19–27. Atti dei Convegni Lincei, No. 17.
  * [21] J. Folkman, _Graphs with monochromatic complete subgraphs in every edge coloring_ , SIAM J. Appl. Math. 18 (1970), 19–24.
  * [22] J. Fox and B. Sudakov, _Density theorems for bipartite graphs and related Ramsey-type results_ , Combinatorica 29 (2009), 153–196.
  * [23] E. Friedgut, V. Rödl, and M. Schacht, _Ramsey properties of random discrete structures_ , Random Structures Algorithms 37 (2010), 407–436.
  * [24] H. Furstenberg and Y. Katznelson, _A density version of the Hales-Jewett theorem_ , J. Anal. Math. 57 (1991), 64–119.
  * [25] R. E. Greenwood and A. M. Gleason, _Combinatorial relations and chromatic graphs_ , Canadian J. Math. 7 (1955), 1–7.
  * [26] D. Haussler and E. Welzl, _$\epsilon$ -nets and simplex range queries_, Discrete Comput. Geom. 2 (1987), 127–151.
  * [27] S. Janson, _Poisson approximation for large deviations_ , Random Structures Algorithms 1 (1990), 221–229.
  * [28] P. Kolaitis, H. J. Prömel, and B. Rothschild, _$K_{l+1}$ -free graphs: asymptotic structure and a $0-1$ law_, Trans. Amer. Math. Soc. 303 (1987), 637–671.
  * [29] J. Komlós, J. Pach, and G. Woeginger, _Almost tight bounds for $\epsilon$-nets_, Discrete Comput. Geom. 7 (1992), 163–173.
  * [30] H. Lefmann, _A note on Ramsey numbers_ , Studia Sci. Math. Hungar. 22 (1987), 445–446.
  * [31] J. Matoušek, R. Seidel, and E. Welzl, _How to net a lot with little: small $\epsilon$-nets for disks and halfspaces_, Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990, pp. 16–22.
  * [32] R. Morris and D. Saxton, _The number of $C_{2\ell}$-free graphs_, Adv. Math. 298 (2016), 534–580.
  * [33] F. Mousset, R. Nenadov, and A. Steger, _On the number of graphs without large cliques_ , SIAM J. Discrete Math. 28 (2014), 1980–1986.
  * [34] R. Nenadov and A. Steger, _A short proof of the random Ramsey theorem_ , Combin. Probab. Comput. 25 (2016), 130–144.
  * [35] J. Nešetřil and V. Rödl, _The Ramsey property for graphs with forbidden complete subgraphs_ , J. Combinatorial Theory Ser. B 20 (1976), 243–249.
  * [36] J. Pach and G. Tardos, _Tight lower bounds for the size of epsilon-nets_ , J. Amer. Math. Soc. 26 (2013), 645–658.
  * [37] H. J. Prömel and A. Steger, _Random $l$-colorable graphs_, Random Structures Algorithms 6 (1995), 21–37.
  * [38] F. P. Ramsey, _On a problem of formal logic_ , Proc. London Math. Soc. (2) 30 (1929), 264–286.
  * [39] V. Rödl, _The dimension of a graph and generalized Ramsey theorems_ , Master’s thesis, Charles University, 1973.
  * [40] V. Rödl, A. Ruciński, and M. Schacht, _An exponential-type upper bound for Folkman numbers_ , Combinatorica 37 (2017), 767–784.
  * [41] by same author, _Ramsey properties of random graphs and Folkman numbers_ , Discuss. Math. Graph Theory 37 (2017), 755–776.
  * [42] D. Saxton and A. Thomason, _Hypergraph containers_ , Invent. Math. 201 (2015), 925–992.
  * [43] by same author, _Simple containers for simple hypergraphs_ , Combin. Probab. Comput. 25 (2016), 448–459.
  * [44] M. Schacht, _Extremal results for random discrete structures_ , Ann. of Math. (2) 184 (2016), 333–365.