On the KŁR conjecture in random graphs

Introduction

Szemerédi’s regularity lemma , which played a crucial role in Szemerédi’s proof of the Erdős-Turán conjecture on long arithmetic progressions in dense subsets of the integers, is one of the most important tools in extremal graph theory (see ). Roughly speaking, it says that the vertex set of every graph $G$ may be divided into a bounded number of parts in such a way that most of the induced bipartite graphs between different parts are pseudorandom.

More precisely, a bipartite graph between sets $U$ and $V$ is said to be $\epsilon$-regular if, for every $U^{\prime}\subseteq U$ and $V^{\prime}\subseteq V$ with $|U^{\prime}|\geq\epsilon|U|$ and $|V^{\prime}|\geq\epsilon|V|$, the density $d(U^{\prime},V^{\prime})$ of edges between $U^{\prime}$ and $V^{\prime}$ satisfies

We will say that a partition of the vertex set of a graph into $t$ pieces $V_{1},\dots,V_{t}$ is an equipartition if, for every $1\leq i,j\leq t$, we have the condition that $||V_{i}|-|V_{j}||\leq 1$. We say that the partition is $\epsilon$-regular if it is an equipartition and, for all but at most $\epsilon t^{2}$ pairs $(V_{i},V_{j})$, the induced graph between $V_{i}$ and $V_{j}$ is $\epsilon$-regular. Szemerédi’s regularity lemma can be formally stated as follows.

For every $\epsilon>0$ and every positive integer $t_{0}$, there exists a positive integer $T$ such that every graph $G$ with at least $t_{0}$ vertices admits an $\epsilon$-regular partition $V_{1},\dots,V_{t}$ of its vertex set into $t_{0}\leq t\leq T$ pieces.

Often the strength of the regularity lemma lies in the fact that it may be combined with a counting or embedding lemma that tells us approximately how many copies of a particular subgraph a graph contains, in terms of the densities $d(V_{i},V_{j})$ arising in an $\epsilon$-regular partition. The so-called regularity method usually works as follows. First, one applies the regularity lemma to a graph $G$. Next, one defines an auxiliary graph $R$ whose vertices are the parts of the regular partition of $G$ one obtains, and whose edges correspond to regular pairs with non-negligible density. (For some applications we may instead take a weighted graph, where the weight of the edge between a regular pair $V_{i}$ and $V_{j}$ is the density $d(V_{i},V_{j})$.) If one can then find a copy of a particular subgraph $H$ in $R$, the counting lemma allows one to find many copies of $H$ in $G$. If $R$ does not contain a copy of $H$, this information can often be used to deduce some further structural properties of the graph $R$ and, thereby, the original graph $G$. Applied in this manner, the regularity and counting lemmas allow one to prove a number of well-known theorems in extremal graph theory, including the Erdős-Stone theorem , its stability version due to Erdős and Simonovits , and the graph removal lemma .

For sparse graphs – that is, graphs with $n$ vertices and $o(n^{2})$ edges – the regularity lemma stated in Theorem 1.1 is vacuous, since every equipartition into a bounded number of parts is $\epsilon$-regular for $n$ sufficiently large. It was observed independently by Kohayakawa and Rödl that the regularity lemma can nevertheless be generalized to an appropriate class of graphs with density tending to zero. Their result applies to a natural class of sparse graphs that is wide enough for the lemma to have several interesting applications. In particular, it applies to relatively dense subgraphs of random graphs – that is, one takes a random graph $G_{n,p}$ of density $p$ and a subgraph $G$ of $G_{n,p}$ of density at least $\delta p$ (or relative density at least $\delta$ in $G_{n,p}$), where $p$ usually tends to 0, while $\delta>0$ is usually independent of the number of vertices.

To make this precise, we say that a bipartite graph between sets $U$ and $V$ is $(\epsilon,p)$-regular if, for every $U^{\prime}\subseteq U$ and $V^{\prime}\subseteq V$ with $|U^{\prime}|\geq\epsilon|U|$ and $|V^{\prime}|\geq\epsilon|V|$, the density $d(U^{\prime},V^{\prime})$ of edges between $U^{\prime}$ and $V^{\prime}$ satisifies

That is, we alter the definition of regularity so that it is relative to a particular density $p$. This density is usually comparable to the total density between $U$ and $V$. A partition of the vertex set of a graph into $t$ pieces $V_{1},\dots,V_{t}$ is then said to be $(\epsilon,p)$-regular if it is an equipartition and, for all but at most $\epsilon t^{2}$ pairs $(V_{i},V_{j})$, the induced graph between $V_{i}$ and $V_{j}$ is $(\epsilon,p)$-regular.

The class of graphs to which the Kohayakawa-Rödl regularity lemma applies are the so-called upper-uniform graphs . Suppose that $0<\eta\leq 1$, $D>1$, and $0<p\leq 1$ are given. We will say that a graph $G$ is $(\eta,p,D)$-upper-uniform if for all disjoint subsets $U_{1}$ and $U_{2}$ with $|U_{1}|,|U_{2}|\geq\eta|V(G)|$, the density of edges between $U_{1}$ and $U_{2}$ satisfies $d(U_{1},U_{2})\leq Dp$. This condition is satisfied for many natural classes of graphs, including all subgraphs of random and pseudorandom graphs of density $p$. The regularity lemma of Kohayakawa and Rödl is the following.

For every $\epsilon,D>0$ and every positive integer $t_{0}$, there exist $\eta>0$ and a positive integer $T$ such that for every $p\in$, every graph $G$ with at least $t_{0}$ vertices that is $(\eta,p,D)$-upper-uniform admits an $(\epsilon,p)$-regular partition $V_{1},\dots,V_{t}$ of its vertex set into $t_{0}\leq t\leq T$ pieces.

The proof of this theorem is essentially the same as the proof of the dense regularity lemma, with the upper uniformity used to ensure that the iteration terminates after a constant number of steps. We note that different versions of the result have appeared in the literature where the $(\eta,p,D)$-upper-uniformity assumption is altered or dropped completely .

As we have already mentioned above, the usefulness of the dense regularity method relies on the existence of a corresponding counting lemma. Roughly speaking, a counting lemma says that if we start with an arbitrary graph $H$ and replace its vertices by large independent sets and its edges by $\epsilon$-regular bipartite graphs with non-negligible density, then this blown-up graph will contain roughly the expected number of copies of $H$. Here is a precise statement to that effect.

For every graph $H$ with vertex set $\{1,2,\dots,k\}$ and every $\delta>0$, there exists $\epsilon>0$ and an integer $n_{0}$ such that the following statement holds. Let $n\geq n_{0}$ and let $G$ be a graph whose vertex set is a disjoint union $V_{1}\cup\ldots\cup V_{k}$ of sets of size $n$. Assume that for each $ij\in E(H)$, the bipartite subgraph of $G$ induced between $V_{i}$ and $V_{j}$ is $\epsilon$-regular and has density $d_{ij}$. Then the number of $k$-tuples $(v_{1},\dots,v_{k})\in V_{1}\times\dots\times V_{k}$ such that $v_{i}v_{j}\in E(G)$ whenever $ij\in E(H)$ is $n^{k}(\prod_{ij\in E(H)}d_{ij}\pm\delta)$.

In particular, if the density $d_{ij}$ is large for every $ij\in E(H)$, then $G$ contains many copies of $H$.

Let us define a canonical copy of $H$ in $G$ to be a $k$-tuple as in the lemma above: that is, a $k$-tuple $(v_{1},\dots,v_{k})$ such that $v_{i}\in V_{i}$ for every $i\in V(H)$ and $v_{i}v_{j}\in E(G)$ for every $ij\in E(H)$. Let us also write $G(H)$ for the number of canonical copies of $H$ in $G$. (Of course, the definitions of “canonical copy” and $G(H)$ depend not just on $G$ but also on the partition of $G$ into $V_{1},\dots,V_{k}$, but we shall suppress this dependence in the notation.)

In order to use Theorem 1.2, one would ideally like a statement similar to Lemma 1.3 but adapted to a sparse context. For this we would have an additional parameter $p$, which can tend to zero with $n$. We would replace the densities $d_{ij}$ by $d_{ij}p$ and we would like to show that $G(H)$ is approximately $n^{k}p^{e(H)}(\prod_{ij\in E(H)}d_{ij}\pm\delta)$. In order to obtain this stronger conclusion (stronger because the error estimate has been multiplied by $p^{e(H)}$), we need a stronger assumption, and the natural assumption, given the statement of Theorem 1.2 (which is itself natural), is to replace $\epsilon$-regularity by $(\epsilon,p)$-regularity.

Of course, we cannot expect such a result if $p$ is too small. Consider the random graph $G$ obtained from $H$ by replacing each vertex of $H$ by an independent set of size $n$ and each edge of $H$ by a random bipartite graph with $pn^{2}$ edges. With high probability, $G(H)$ will be about $p^{e(H)}n^{v(H)}$. Hence, if $p^{e(H)}n^{v(H)}\ll pn^{2}$, then one can remove all copies of $H$ from $G$ by deleting a tiny proportion of all edges. (We may additionally delete a further small proportion of edges to ensure that all bipartite graphs corresponding to the edges of $H$ have the same number of edges.) It is not hard to see that with high probability the bipartite graphs that make up the resulting graph $G^{\prime}$ will be $(\epsilon,q)$-regular for some $q=(1-o(1))p$, but that $G^{\prime}$ will contain no canonical copies of $H$.

Therefore, a sparse analogue of Lemma 1.3 cannot hold if $p\leq cn^{-\frac{v(H)-2}{e(H)-1}}$ for some small positive constant $c$. Note that one can replace $H$ in the above argument by an arbitrary subgraph $H^{\prime}\subseteq H$, since removing all copies of $H^{\prime}$ from a graph also results in a $H$-free subgraph. This observation naturally leads to the notion of $2$-density $m_{2}(H)$ of a graph $H$, defined by

(We take $m_{2}(K_{2})=\frac{1}{2}$.) With this notation, what we have just seen is that to have any chance of an appropriate analogue of Lemma 1.3 holding, we need to assume that $p\geq Cn^{-1/m_{2}(H)}$ for some absolute constant $C>0$.

Unfortunately, there is a more fundamental difficulty with finding a sparse counting lemma to match a sparse regularity lemma. Instead of sparse random graphs with many vertices, one can consider blow-ups of sparse random graphs with far fewer vertices. That is, one can pick a counterexample of the kind just described but with the sets $V_{i}$ of size $r$ for some $r$ that is much smaller than $n$, and then one can replace each vertex of this small graph by an independent set of $n/r$ vertices to make a graph with $n$ vertices in each $V_{i}$. Roughly speaking, the counterexample above survives the blowing-up process, and the result is that the hoped-for sparse counting lemma is false whenever $p=o(1)$. (For more details, see .)

However, these “block” counterexamples have a special structure, so, for $p\geq Cn^{-1/m_{2}(H)}$, it looks plausible that graphs for which the sparse counting lemma fails should be very rare. This intuition was formalized by Kohayakawa, Łuczak, and Rödl , who made a conjecture that is usually known as the KŁR conjecture. Before we state it formally, let us introduce some notation.

As above, let $H$ be a graph with vertex set $\{1,2,\dots,k\}$. We denote by $\mathcal{G}(H,n,m,p,\epsilon)$ the collection of all graphs $G$ obtained in the following way. The vertex set of $G$ is a disjoint union $V_{1}\cup\ldots\cup V_{k}$ of sets of size $n$. For each edge $ij\in E(H)$, we add to $G$ an $(\epsilon,p)$-regular bipartite graph with $m$ edges between the pair $(V_{i},V_{j})$. These are the only edges of $G$. Let us also write $\mathcal{G}^{*}(H,n,m,p,\epsilon)$ for the set of all $G\in\mathcal{G}(H,n,m,p,\epsilon)$ that do not contain a canonical copy of $H$.

Since the sparse regularity lemma yields graphs with varying densities between the various pairs of vertex sets, it may seem surprising that we are restricting attention to graphs where all the densities are equal (to $m/n^{2}$). However, as we shall see later, it is sufficient to consider just this case. In fact, the KŁR conjecture is more specific still, since it takes all the densities to be equal to $p$. Again, it turns out that from this case one can deduce the other cases that are needed.

Let $H$ be a fixed graph and let $\beta>0$. Then there exist $C,\epsilon>0$ and a positive integer $n_{0}$ such that

for every $n\geq n_{0}$ and every $m\geq Cn^{2-1/m_{2}(H)}$.

Note that $\binom{n^{2}}{m}^{e(H)}$ is the number of graphs with vertex set $V_{1}\cup\dots\cup V_{k}$ with $m$ edges between each pair $(V_{i},V_{j})$ when $ij\in E(H)$ and no edges otherwise. Thus, we can interpret the conjecture as follows: the probability that a random such graph belongs to the bad set $\mathcal{G}^{*}(H,n,m,m/n^{2},\epsilon)$ is at most $\beta^{m}$.

The rough idea of the conjecture is that the probability that a graph is bad is so small that a simple union bound tells us that with high probability a random graph does not contain any bad graph – which implies that we may use the sparse embedding lemma we need. In other words, $(\epsilon,p)$-regularity on its own does not suffice, but if you know in addition that your graph is a subgraph of a sparse random graph, then with high probability it does suffice.

More precisely, let $G$ be a random graph with $N$ vertices and edge probability $p$ and let $n=\eta N$ and $m=dpn^{2}\geq n$. Then the expected number of subgraphs of $G$ of the form $\mathcal{G}^{*}(H,n,m,p,\epsilon)$ is at most

Therefore, choosing $\beta$ to be sufficiently small in terms of $d,\eta$, and $H$, the probability that $G$ contains a graph in $\mathcal{G}^{*}(H,n,m,p,\epsilon)$ is very small. By summing over the possible values of $n$ and $m$, we may rule out such bad subgraphs for all $n$ and $m$ with $n\geq\eta N$ and $m\geq dpn^{2}$.

This does not give us a counting lemma for $(\epsilon,p)$-regular subgraphs of $G$, but it does at least tell us that every $(\epsilon,p)$-regular subgraph of $G$ with sufficiently dense pairs in the right places contains a canonical copy of $H$. In other words, it gives us an embedding lemma, which makes it suitable for several applications to embedding results. For example, as noted in , it is already sufficiently strong that a straightforward application of the sparse regularity lemma then allows one to derive the following theorem, referred to as Turán’s theorem for random graphs, which was eventually proved in a different way by Conlon and Gowers (for strictly balanced graphs, i.e., those for which $m_{2}(H)>m_{2}(H^{\prime})$ for every proper subgraph $H^{\prime}$ of $H$) and, independently, Schacht (see also ). We remark that this theorem was the original motivation behind Conjecture 1.4 – see Section 6 of . Following , let us say that a graph $G$ is $(H,\epsilon)$-Turán if every subgraph of $G$ with at least

edges contains a copy of $H$. Here $\chi(H)$ is the chromatic number of $H$.

For every $\epsilon>0$ and every graph $H$, there exist positive constants $c$ and $C$ such that

The KŁR conjecture has attracted considerable attention over the past two decades and has been verified for a number of small graphs. It is straightforward to verify that it holds for all graphs $H$ that do not contain a cycle. In this case, the class $\mathcal{G}^{*}(H,n,m,p,\epsilon)$ will be empty. The cases $H=K_{3}$, $K_{4}$, and $K_{5}$ were resolved in , , and , respectively. In the case when $H$ is a cycle, the conjecture was proved in (see also for a slightly weaker version). Very recently, it was proved for all balanced graphs, that is, those graphs $H$ for which $m_{2}(H)=\frac{e(H)-1}{v(H)-2}$, by Balogh, Morris, and Samotij and by Saxton and Thomason in full generality.

Besides implying Theorem 1.5, Conjecture 1.4 is also sufficient for transferring many other classical extremal results about graphs to subgraphs of the random graph $G_{n,p}$, including Ramsey’s theorem and the Erdős-Simonovits stability theorem . However, there are situations where an embedding result is not enough: rather than just a single copy of $H$, one needs to know that there are many copies. That is, one needs something more like a full counting lemma. In this paper, we shall state and prove such a “counting version” of the KŁR conjecture for subgraphs of random graphs. Later in the paper we shall give examples of classical theorems whose sparse random versions do not follow from the KŁR conjecture but do follow from our counting result.

For every graph $H$ and every $\delta,d>0$, there exist $\epsilon,\xi>0$ with the following property. For every $\eta>0$, there is a $C>0$ such that if $p\geq CN^{-1/m_{2}(H)}$, then a.a.s. the following holds in $G_{N,p}$:

For every $n\geq\eta N$, $m\geq dpn^{2}$, and every subgraph $G$ of $G_{N,p}$ in $\mathcal{G}(H,n,m,p,\epsilon)$,

Moreover, if $H$ is strictly balanced, that is, if $m_{2}(H)>m_{2}(H^{\prime})$ for every proper subgraph $H^{\prime}$ of $H$, then

Note that strictly speaking the statements above depend not just on the graph $G$ but on the partition $V_{1}\cup\dots\cup V_{k}$ that causes $G$ to belong to $\mathcal{G}(H,n,m,p,\epsilon)$. Roughly speaking, (i) tells us that if $G$ contains “many” edges in the right places, then there are “many” copies of $H$, while (ii) tells us that the number of copies of $H$ is roughly what one would expect for a random graph with pairs of the same densities. We note that a result similar to (ii) holds for all graphs if one is willing to allow some extra logarithmic factors. We will say more about this in the concluding remarks.

The proof of part (i) employs the ideas of Schacht , as modified by Samotij , and as a result part (i) holds with probability at least $1-\exp(-bpN^{2})$ for some $b>0$ depending on $H,\eta$, and $d$. Part (ii) is proved using the results of Conlon and Gowers and hence hold with probability at least $1-N^{-B}$ for any fixed $B>0$, provided that $C$ and $N$ are sufficiently large. Since part (ii) gives an upper bound as well as a lower bound, standard results on upper tail estimates imply that the result cannot hold with the same exponential probability as part (i) (see, for example, ).

We note that weaker versions of Theorem 1.6, applicable for larger values of $p$, may be found in some earlier papers on the KŁR conjecture and Turán’s theorem and more recent work on sparse regularity in pseudorandom graphs . We also believe that a variant of part (i) of Theorem 1.6 may be derivable from the work of Saxton and Thomason , though they have not stated it in these terms.

It is not hard to show that Theorem 1.6, like Conjecture 1.4, implies the best possible sparse random analogues of many classical theorems in extremal graph theory. In particular, it implies Theorem 1.5 above. It also implies the following sparse random version of the Erdős-Simonovits stability theorem, which was first proved by Conlon and Gowers for all strictly balanced graphs and later extended to general $H$ by Samotij , who adapted Schacht’s method for this purpose.

For every graph $H$ and every $\delta>0$, there exist $\epsilon,C>0$ such that if $p\geq Cn^{-1/m_{2}(H)}$, then a.a.s. every $H$-free subgraph $G^{\prime}\subseteq G_{n,p}$ with $e(G^{\prime})\geq\left(1-\frac{1}{\chi(H)-1}-\epsilon\right)\binom{n}{2}p$ may be made $(\chi(H)-1)$-partite by removing at most $\delta pn^{2}$ edges.

Another easy consequence of Theorem 1.6 is the $1$-statement of the following sparse Ramsey theorem, originally proved by Rödl and Ruciński in 1995. We remark here that the $1$-statement of Theorem 1.8 below also extends to general hypergraphs . Following , we say that a graph $G$ is $(H,r)$-Ramsey if every $r$-colouring of the edges of $G$ yields a monochromatic copy of $H$.

For every graph $H$ that is not a star forest or a path of length $3$ and for every positive integer $r\geq 2$, there exist constants $c,C>0$ such that

We will omit the deductions of Theorem 1.7 and the $1$-statements of Theorems 1.5 and 1.8 from Theorem 1.6. These are fairly standard applications of the regularity method (see, for example, ).

2 A sparse removal lemma for graphs

The triangle removal lemma of Ruzsa and Szemerédi states that for every $\delta>0$ there exists an $\epsilon>0$ such that if $G$ is any graph on $n$ vertices that contains at most $\epsilon n^{3}$ triangles, then $G$ may be made triangle-free by removing at most $\delta n^{2}$ edges. Despite its innocent appearance, this result has several striking consequences. Most notably, it easily implies Roth’s theorem on $3$-term arithmetic progressions in dense subsets of the integers. For general graphs $H$, a similar statement holds (see also ): if an $n$-vertex graph contains $o(n^{v(H)})$ copies of $H$, then it may be made $H$-free by removing $o(n^{2})$ edges. This result is known as the graph removal lemma. A sparse random version of the graph removal lemma was conjectured by Łuczak in and proved, for strictly balanced $H$, by Conlon and Gowers . Here, we apply our main result, Theorem 1.6, to extend this result to all graphs $H$.

For every $\delta>0$ and every graph $H$, there exist positive constants $\epsilon$ and $C$ such that if $p\geq Cn^{-1/m_{2}(H)}$, then the following holds a.a.s. in $G_{n,p}$. Every subgraph of $G_{n,p}$ which contains at most $\epsilon p^{e(H)}n^{v(H)}$ copies of $H$ may be made $H$-free by removing at most $\delta pn^{2}$ edges.

Note that if $p\leq cn^{-1/m_{2}(H)}$ for a sufficiently small positive constant $c$ (depending on $H$ and $\delta$), then $H$ has a subgraph $H^{\prime}$, the expected number of copies of which is at most $\delta pn^{2}$, so we can remove all copies of $H$ by deleting an edge from each copy of $H^{\prime}$. Thus, it is natural to conjecture, as Łuczak did, that Theorem 1.9 actually holds for all values of $p$. For balanced graphs, we may close the gap by taking $\epsilon$ to be sufficiently small in terms of $C$, $\delta$, and $H$. For $p\leq Cn^{-1/m_{2}(H)}$ and $\epsilon<\delta C^{-e(H)}$, the number of copies of $H$ is at most $\epsilon p^{e(H)}n^{v(H)}\leq\epsilon C^{e(H)}pn^{2}<\delta pn^{2}$. Deleting an edge from each copy of $H$ yields the result.

3 The clique density theorem

For any $\rho>0$, let $g_{k}(\rho,n)$ be the minimum number of copies of $K_{k}$ which are contained in any graph on $n$ vertices with density at least $\rho$. We then take

Complete $(k-1)$-partite graphs demonstrate that $g_{k}(\rho)=0$ for $\rho\leq 1-\frac{1}{k-1}$. On the other hand, a robust version of Turán’s theorem known as supersaturation tells us that $g_{k}(\rho)>0$ for all $\rho>1-\frac{1}{k-1}$.

There has been much work on determining $g_{k}(\rho)$ above the natural threshold $1-\frac{1}{k-1}$, but it is only in recent years that the exact dependency of $g_{k}(\rho)$ on $\rho$ has been found for any $k\geq 3$. For $k=3$ and the interval $\frac{1}{2}\leq\rho\leq\frac{2}{3}$, this was accomplished by Fisher , while for a general $\rho$ the value of $g_{3}(\rho)$ was determined by Razborov using flag algebras. Employing different methods, Nikiforov reproved the $k=3$ case and also solved the case $k=4$. Finally, Reiher recently resolved the general case.

We will show that an analogous theorem holds within the random graph $G_{n,p}$. We note that this theorem, Theorem 1.10 below, also follows as a direct application of the results of . To state the result, we define, for a subgraph $G^{\prime}$ of $G_{n,p}$, the relative density of $G^{\prime}$ in $G_{n,p}$ to be $e(G^{\prime})/p\binom{n}{2}$.

For any $k\geq 3$ and any $\epsilon>0$, there exists a constant $C>0$ such that if $p\geq Cn^{-2/(k+1)}$, then the following holds a.a.s. in $G_{n,p}$. Any subgraph $G^{\prime}$ of $G_{n,p}$ will contain at least $(g_{k}(\rho)-\epsilon)p^{\binom{k}{2}}\binom{n}{k}$ copies of $K_{k}$, where $\rho$ is the relative density of $G^{\prime}$ in $G_{n,p}$.

We remark that, as $m_{2}(K_{k})=(k+1)/2$, the assumption on $p$ in the above theorem is best possible up to the value of the constant $C$. Using part (ii) of Theorem 1.6, we may show that a similar theorem also holds for any strictly balanced graph $H$. That is, if $g_{H}(\rho)$ is the natural analogue of $g_{k}(\rho)$ defined for $H$, then for any $\epsilon>0$, there exists a $C>0$ such that if $p\geq Cn^{-1/m_{2}(H)}$, the random graph $G_{n,p}$ will a.a.s. be such that any subgraph $G^{\prime}$ of $G_{n,p}$ contains at least $(g_{H}(\rho)-\epsilon)p^{e(H)}\frac{n^{v(H)}}{Aut(H)}$ copies of $H$, where again $\rho$ is the relative density of $G^{\prime}$ in $G_{n,p}$. However, the function $g_{H}(\rho)$ is only well understood for cliques and certain classes of bipartite graph (see, for example, ).

4 The Hajnal-Szemerédi theorem

Let $H$ be a fixed graph on $h$ vertices. An arbitrary collection of vertex-disjoint copies of $H$ in some larger graph is called an $H$-packing. A perfect $H$-packing (or $H$-factor) is an $H$-packing that covers all vertices of the host graph. It has long been known for certain graphs $H$ that if the minimum degree of an $n$-vertex graph $G$ is sufficiently large and $n$ is divisible by $h$, then $G$ contains an $H$-factor. For example, Dirac’s theorem implies that if $H$ is a path of length $h-1$, $n$ is divisible by $h$, and $\delta(G)\geq n/2$, then $G$ contains an $H$-factor. Corrádi and Hajnal proved that $\delta(G)\geq 2n/3$ implies the existence of a $K_{3}$-factor in $G$. A milestone in this area of research, the famous theorem of Hajnal and Szemerédi , states that the condition $\delta(G)\geq(1-\frac{1}{k})n$ is sufficient to guarantee a perfect $K_{k}$-packing in $G$ for an arbitrary $k$ (see for a short proof of this theorem).

For any $k\geq 3$, every $n$-vertex graph $G$ with $\delta(G)\geq(1-\frac{1}{k})n$ contains a $K_{k}$-factor, provided that $n$ is divisible by $k$.

This theorem has also been generalized to arbitrary $H$ . In particular, a result of Komlós shows that a parameter known as the critical chromatic number governs the existence of almost perfect packings (i.e., packings covering all but a $o(1)$-fraction of the vertices of the host graph) in graphs of large minimum degree.

We will prove the following approximate version of the Hajnal-Szemerédi Theorem in the random graph $G_{n,p}$.

For any $k\geq 3$ and any $\gamma>0$, there exists a constant $C>0$ such that if $p\geq Cn^{-2/(k+1)}$, then the following holds a.a.s. in $G_{n,p}$. Any subgraph $G^{\prime}$ of $G_{n,p}$ with $\delta(G^{\prime})\geq(1-\frac{1}{k}+\gamma)pn$ contains a $K_{k}$-packing that covers all but at most $\gamma n$ vertices.

We remark that the assumption on $p$ in the above theorem is best possible up to the value of the constant $C$. Using the result of Komlós , we may show that a similar theorem also holds for any graph $H$. That is, for any $H$ and any $\gamma>0$, there exists a $C>0$ such that if $p\geq Cn^{-1/m_{2}(H)}$, then a.a.s. every subgraph $G^{\prime}$ of $G_{n,p}$ satisfying $\delta(G^{\prime})\geq(1-\frac{1}{\chi_{\text{cr}}(H)}+\gamma)pn$, where $\chi_{\text{cr}}(H)$ is the critical chromatic number of $H$, contains an $H$-packing covering all but at most $\gamma n$ vertices.

Finally, we remark that the problem of finding perfect packings in subgraphs of random graphs seems to be much more difficult. On the positive side, a best possible sparse random analogue of Dirac’s theorem was recently proved by Lee and Sudakov . On the negative side, it was observed by Huang, Lee, and Sudakov that for every $\epsilon>0$, there are $c,C>0$ such that if every vertex of $H$ is contained in a triangle and $Cn^{-1/2}\leq p\leq c$, then $G_{n,p}$ a.a.s. contains a spanning subgraph $G^{\prime}$ with $\delta(G^{\prime})\geq(1-\epsilon)pn$ such that at least $\epsilon p^{-2}/3$ vertices of $G^{\prime}$ are not contained in a copy of $H$. Therefore, the presence of the set of uncovered vertices in the statement of Theorem 1.12 is indispensable. For further discussion and related results, we refer the reader to .

5 The Andrásfai-Erdős-Sós theorem

A result of Zarankiewicz states that if a graph on $n$ vertices has minimum degree at least $(1-\frac{1}{k-1})n$ then it contains a copy of $K_{k}$. This result follows immediately from Turán’s theorem but is interesting because it has a surprisingly robust stability version, due to Andrásfai, Erdős, and Sós . This theorem states that any $K_{k}$-free graph on $n$ vertices with minimum degree at least $(1-\frac{3}{3k-4})n$ must be $(k-1)$-partite.

This result was extended to general graphs by Alon and Sudakov (see also ), who showed that for any graph $H$ and any $\gamma>0$, every $H$-free graph on $n$ vertices with minimum degree at least $\left(1-\frac{3}{3\chi(H)-4}+\gamma\right)n$ may be made $(\chi(H)-1)$-partite by deleting $o(n^{2})$ edges. We prove a random analogue of this result, as follows.

For every graph $H$ and every $\gamma>0$, there exists $C>0$ such that if $p\geq Cn^{-1/m_{2}(H)}$, then a.a.s. every $H$-free subgraph $G^{\prime}\subseteq G_{n,p}$ with $\delta(G^{\prime})\geq\left(1-\frac{3}{3\chi(H)-4}+\gamma\right)pn$ may be made $(\chi(H)-1)$-partite by removing from it at most $\gamma pn^{2}$ edges.

More generally, for any $H$ and any $r$, we may define

The Andrásfai-Erdős-Sós theorem determines the value of $\delta_{\chi}(K_{k},k-1)$, but there are also some results known for other values of $r$. For example, it is known that $\delta_{\chi}(K_{3},3)=\frac{10}{29}$ and $\delta_{\chi}(K_{3},4)=\frac{1}{3}$. Our methods easily allow us to transfer any such results about $\delta_{\chi}(H,r)$ to the random setting. These are approximate results, proving that any $H$-free graph with a certain minimum degree is close to a graph with bounded chromatic number. As noted in , one cannot hope to achieve a more exact result saying that the graph itself has bounded chromatic number.

KŁR conjecture via multiple exposure

In this section, we prove part (i) of Theorem 1.6. The proof follows the ideas of . The main idea in these proofs is to expose the random graph in multiple rounds. In this context, this can be traced back to the work of Rödl and Ruciński in .

We now deduce the first part of Theorem 1.6 from Theorem 2.1.

Let $H$ be an arbitrary $k$-vertex graph and let $d>0$. We may assume that $H$ contains a vertex of degree at least two (and hence $m_{2}(H)\geq 1$) since otherwise the assertion of the theorem is trivial. Let

Moreover, let $\xi^{\prime}=\xi_{\ref{thm:part-i}}(H,d/2)$ and let $\xi=2^{-e(H)}\xi^{\prime}$. Next, fix an arbitrary positive constant $\eta$ and let $C=\max\{C^{\prime},40k\}\cdot\eta^{-2}$. Assume that $p\geq CN^{-1/m_{2}(H)}$ and that $N$ is sufficiently large. Finally, let $n\geq\eta N$ and let $m\geq dpn^{2}$. We estimate the probability of the event (we denote it by $\mathcal{B}$) that $G_{N,p}$ contains a subgraph $G\in\mathcal{G}(H,n,m,p,\epsilon)$ with $G(H)<\xi\left(\frac{m}{n^{2}}\right)^{e(H)}n^{v(H)}$.

Let $W_{1},\ldots,W_{k}$ be pairwise disjoint subsets of $V(G_{N,p})$, each of size $n$, and let $\mathcal{B}(W_{1},\ldots,W_{k})$ denote the event that $G_{N,p}$ contains a subgraph $G$ as above with sets $W_{1},\ldots,W_{k}$ playing the role of $V_{1},\ldots,V_{k}$ from the definition of $\mathcal{G}(H,n,m,p,\epsilon)$. By Chernoff’s inequality (see below),

is at most $\exp(-bpn^{2})$. To see this, note that $H(W_{1},\ldots,W_{k})_{p}$ has the same distribution as $G_{N,p}\cap H(W_{1},\ldots,W_{k})$ and that our assumptions imply that $p\geq CN^{-1/m_{2}(H)}\geq C^{\prime}n^{-1/m_{2}(H)}$. It follows that

since $pn^{2}\geq\eta^{2}pN^{2}\geq C\eta^{2}N^{2-1/m_{2}(H)}\geq 40kN$. ∎

Note that we used Chernoff’s bound in the following standard form (see, for example, [5, Appendix A]).

Let $t$ be a positive integer, $p\in$, and $X\sim Bin(t,p)$. For every positive $a$,

In particular, if we apply the upper tail estimate with $a=pt/2$, we see that

as required in the proof above with $t=n^{2}$.

In the proof of Theorem 2.1, we will also need the following approximate concentration result for random subgraphs of $H(n)$, the complete blow-up of $H$ obtained by replacing the vertices of $H$ by disjoint sets $V_{1},\ldots,V_{k}$ of size $n$ each and the edges of $H$ by complete bipartite graphs. Lemma 2.3 below is [79, Proposition 3.6] with $H_{n}$ being the $e(H)$-uniform hypergraph on the vertex set $E(H(n))$ whose edges are the canonical copies of $H$ in $H(n)$. The proof of the fact that this hypergraph is $(K,n^{-1/m_{2}(H)})$-bounded, see [79, Definition 3.2], is implicit in the proof of the $1$-statement of [79, Theorem 2.7]. The definition of $\deg_{H^{\prime}}$ is given in Section 2.2.2.

Let $H$ be an arbitrary graph with $\Delta(H)\geq 2$. There exists a $K>0$ such that for every proper $H^{\prime}\subseteq H$ and every $\eta>0$, there exist $b>0$ and an integer $n_{0}$ such that for every $n\geq n_{0}$, if $p\geq n^{-1/m_{2}(H)}$, then with probability at least $1-\exp(-bpn^{2})$, for every $ij\in E(H)\setminus E(H^{\prime})$ there exists a subgraph $X\subseteq H(n)_{p}$ with $|X|\leq\eta pn^{2}$ satisfying

Let $H$ be an arbitrary graph and let $d$ be a positive constant. In the remainder of this section, we prove Theorem 2.1 by induction on the number of edges in $H^{\prime}$.

Let $H^{\prime}$ be the empty subgraph of $H$ and note that, regardless of $G^{\prime}$, we have $|\mathcal{C}(H,G;H^{\prime},G^{\prime})|=G(H)$. The base of the induction follows immediately from the following one-sided version of the counting lemma, Lemma 1.3, if we let $\epsilon=\epsilon_{\ref{lemma:H-count-lower}}(d)$, $\xi=\xi_{\ref{lemma:H-count-lower}}(d)$, $b=1$, $C=1$, and $n_{0}=1$.

In fact, by choosing $\epsilon$ sufficiently small, one can show that $\xi\geq d^{e(H)}-\delta$.

2 Induction step

Let $H^{\prime\prime}$ be an arbitrary subgraph of $H^{\prime}$ with $e(H^{\prime})-1$ edges. Let $\epsilon$, $\xi^{\prime}$, $b^{\prime}$, $C^{\prime}$, and $n_{0}^{\prime}$ be the constants whose existence is asserted by the inductive assumption with $H^{\prime}$ replaced by $H^{\prime\prime}$ and $d$ replaced by $d/4$, i.e., let

We also let $K=K_{\ref{lemma:part-i-upper-tail}}(H)$, $\eta=\epsilon^{2}d/8$, and $\hat{b}=b_{\ref{lemma:part-i-upper-tail}}(H,H^{\prime\prime},\eta)$. Furthermore, let

Let $\mathcal{S}$ denote the event that the random graph $G_{p}$ possesses the postulated property:

Following Samotij , we will consider a richer probability space that is in a natural correspondence with the space $\mathcal{P}(G)$ of all subgraphs of $G$ equipped with the obvious probability measure $\mathop{\rm Pr}\nolimits$, i.e., the distribution of the random graph $G_{p}$. To this end, let $p_{1},\ldots,p_{R}\in$ be the unique numbers that satisfy

The richer probability space will be the space $\mathcal{P}(G)^{R}$ equipped with the product measure $\mathop{\rm Pr}\nolimits^{*}$ that is the distribution of the sequence $(G_{p_{1}},\ldots,G_{p_{R}})$ of independent random variables, where for each $s$, the variable $G_{p_{s}}$ is a $p_{s}$-random subgraph of $G$. Crucially, observe that due to our choice of $p_{1},\ldots,p_{s}$, see (4), the natural mapping

is measure preserving, i.e., for every $G_{0}\subseteq G$,

In other words, the variables $G_{p}$ and $G_{p_{1}}\cup\ldots\cup G_{p_{R}}$ have the same distribution. Finally, let $d^{*}=d/2$ and consider the following event in the space $\mathcal{P}(G)^{R}$:

There are two reasons why we consider the probability space $\mathcal{P}(G)^{R}$. The first reason is that the probability of $\mathcal{S}^{*}$ is much easier to estimate than the probability of $\mathcal{S}$. The second reason is that a lower bound on $\mathop{\rm Pr}\nolimits^{*}(\mathcal{S}^{*})$ implies a (marginally weaker) lower bound on $\mathop{\rm Pr}\nolimits(\mathcal{S})$, which we show below.

1-\mathop{\rm Pr}\nolimits(\mathcal{S})\leq 2\cdot\big{(}1-\mathop{\rm Pr}\nolimits^{*}(\mathcal{S}^{*})\big{)}.

Note that in order to prove the claim, it suffices to show that

for every $\hat{G}$ that does not satisfy $\mathcal{S}$. Indeed, assuming that (6) holds for every such $\hat{G}$, we have

Since $p_{s}\geq p/(RL^{R})\geq Cn^{-1/m_{2}(H)}/(RL^{R})\geq 32n^{-1}/(\epsilon^{2}d)$, the claimed estimate follows from the union bound, provided that $n$ is sufficiently large. ∎

In the remainder of the proof, we will work in the space $\mathcal{P}(G)^{R}$ and estimate the probability of the event $\mathcal{S}^{*}$, that is, $\mathop{\rm Pr}\nolimits^{*}(\mathcal{S}^{*})$. Let $G_{p_{1}},\ldots,G_{p_{R}}$ be independent random subgraphs of $G$. Given $G_{1}^{\prime}\subseteq G_{p_{1}},\ldots,G_{R}^{\prime}\subseteq G_{p_{R}}$, let

Let $ij$ be the edge of $H^{\prime}$ that is missing in $H^{\prime\prime}$ and let $V_{i}$ and $V_{j}$ be the subsets of $V(G)$ corresponding to the vertices $i$ and $j$, respectively. We consider the set $Z_{s}$ of ‘rich’ edges of $G(V_{i},V_{j})$ that belong to many copies of $H$ from $\mathcal{C}(H,G;H^{\prime\prime},G_{s}^{\prime})$, which we define by

Now comes the key step in the proof. We show that with very high probability, for every $s\in[R]$, regardless of $G(s-1)$ and $G^{\prime}(s-1)$, either $\mathcal{C}(H,G;H^{\prime},G_{1}^{\prime}\cup\ldots\cup G_{s}^{\prime})$ is large or the set $Z(s)$ of ‘rich’ edges grows by more than $n^{2}/R$, that is, $|Z(s)\setminus Z(s-1)|\geq n^{2}/R$.

Then for every $\hat{G}\in\mathcal{P}(G)^{s-1}$,

where $\mathop{\rm Pr}\nolimits^{*}(\mathcal{S}^{*}_{G^{\prime}(0)}\mid G(0)=\hat{G})=\mathop{\rm Pr}\nolimits^{*}(\mathcal{S}^{*}_{G^{\prime}(0)})$.

2.3 Deducing Theorem 2.1 from Claims 2.5 and 2.6

For every $s\in[R]$, let $\mathcal{A}_{s}$ denote the event that $e(G_{p_{s}})\leq 2p_{s}e(G)$ and let $\mathcal{A}(s)=\mathcal{A}_{1}\cap\ldots\cap\mathcal{A}_{s}$. Observe that by (4),

By Chernoff’s inequality, (4), (5), and the fact that $e(G)\geq e(H)dn^{2}$,

Now, for every $s\in[R]$, let $\mathcal{S}_{s}^{*}$ denote the event that $\mathcal{A}(s-1)$ holds and $\mathcal{S}_{G^{\prime}(s-1)}^{*}$ holds for all $G^{\prime}(s-1)\subseteq G(s-1)$. Here, $G^{\prime}(s-1)\subseteq G(s-1)$ means that inclusion holds coordinate-wise. Observe that if $\mathcal{S}_{s}^{*}$ holds for all $s\in[R]$, then $\mathcal{S}^{*}$ must hold since (8) in Claim 2.6 can occur at most $R-1$ times, see (3). Let