Combinatorial theorems in sparse random sets

Introduction

In recent years there has been a trend in combinatorics towards proving that certain well-known theorems, such as Ramsey’s theorem, Turán’s theorem and Szemerédi’s theorem, have “sparse random” analogues. For instance, the first non-trivial case of Turán’s theorem asserts that a subgraph of $K_{n}$ with more than $\lfloor n/2\rfloor\lceil n/2\rceil$ edges must contain a triangle. A sparse random analogue of this theorem is the assertion that if one defines a random subgraph $G$ of $K_{n}$ by choosing each edge independently at random with some very small probability $p$, then with high probability every subgraph $H$ of $G$ such that $|E(H)|\geq\left(\frac{1}{2}+\epsilon\right)|E(G)|$ will contain a triangle. Several results of this kind have been proved, and in some cases, including this one, the exact bounds on what $p$ one can take are known up to a constant factor.

The greatest success in this line of research has been with analogues of Ramsey’s theorem . Recall that Ramsey’s theorem (in one of its many forms) states that, for every graph $H$ and every natural number $r$, there exists $n$ such that if the edges of the complete graph $K_{n}$ are coloured with $r$ colours, then there must be a copy of $H$ with all its edges of the same colour. Such a copy of $H$ is called monochromatic.

Let us say that a graph $G$ is $(H,r)$-Ramsey if, however the edges of $G$ are coloured with $r$ colours, there must be a monochromatic copy of $H$. After efforts by several researchers , most notably Rödl and Ruciński, the following impressive theorem, a “sparse random version” of Ramsey’s theorem, is now known. We write $G_{n,p}$ for the standard binomial model of random graphs, where each edge in an $n$-vertex graph is chosen independently with probability $p$. We also write $v_{H}$ and $e_{H}$ for the number of vertices and edges, respectively, in a graph $H$.

Let $r\geq 2$ be a natural number and let $H$ be a graph that is not a forest consisting of stars and paths of length $3$. Then there exist positive constants $c$ and $C$ such that

That is, given a graph $G$ that is not a disjoint union of stars and paths of length $3$, there is a threshold at approximately $p=n^{-1/m_{2}(H)}$ where the probability that the random graph $G_{n,p}$ is $(H,r)$-Ramsey changes from 0 to 1.

This theorem comes in two parts: the statement that above the threshold the graph is almost certainly $(H,r)$-Ramsey and the statement that below the threshold it almost certainly is not. We shall follow standard practice and call these the 1-statement and the 0-statement, respectively.

There have also been some efforts towards proving sparse random versions of Turán’s theorem, but these have up to now been less successful. Turán’s theorem , or rather its generalization, the Erdős-Stone-Simonovits theorem (see for example ), states that if $H$ is some fixed graph, then any graph with $n$ vertices that contains more than

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

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$. One may then ask for the threshold at which a random graph becomes $(H,\epsilon)$-Turán. The conjectured answer is that the threshold is the same as it is for the corresponding Ramsey property.

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

A difference between this conjecture and Theorem 1.1 is that the 0-statement in this conjecture is very simple to prove. To see this, suppose that $p$ is such that the expected number of copies of $H$ in $G_{n,p}$ is significantly less than the expected number of edges in $G_{n,p}$. Then, since the number of copies of $H$ and the number of edges are both concentrated around their expectations, we can almost always remove a small number of edges from $G_{n,p}$ and get rid of all copies of $H$, which proves that $G_{n,p}$ is not $(H,\epsilon)$-Turán. The expected number of copies of $H$ (if we label the vertices of $H$) is approximately $n^{v_{H}}p^{e_{H}}$, while the expected number of edges in $G_{n,p}$ is approximately $pn^{2}$. The former becomes less than the latter when $p=n^{-(v_{H}-2)/(e_{H}-1)}$.

A further observation raises this bound. Suppose, for example, that $H$ is a triangle with an extra edge attached to one of its vertices. It is clear that the real obstacle to finding copies of $H$ is finding triangles: it is not hard to add edges to them. More generally, if $H$ has a subgraph $K$ with $\frac{e_{K}-1}{v_{K}-2}>\frac{e_{H}-1}{v_{H}-2}$, then we can increase our estimate of $p$ to $n^{-(v_{K}-2)/(e_{K}-1)}$, since if we can get rid of copies of $K$ then we have got rid of copies of $H$. Beyond this extra observation, there is no obvious way of improving the bound for the 0-statement, which is why it is the conjectured upper bound as well.

An argument along these lines does not work at all for the Ramsey property, since if one removes a few edges in order to eliminate all copies of $H$ in one colour, then one has to give them another colour. Since the set of removed edges is likely to look fairly random, it is not at all clear that this can be done in such a way as to eliminate all monochromatic copies of $H$.

Conjecture 1.2 is known to be true for some graphs, for example $K_{3}$, $K_{4}$, $K_{5}$ (see , respectively) and all cycles (see ), but it is open in general. Some partial results towards the general conjecture, where the $1$-statement is proved with a weaker exponent, have been given by Kohayakawa, Rödl and Schacht and Szabó and Vu . The paper of Szabó and Vu contains the best known upper bound in the case where $H$ is the complete graph $K_{t}$ for some $t\geq 6$; the bound they obtain is $p=n^{-1/(t-1.5)}$, whereas the conjectured best possible bound is $p=n^{-2/(t+1)}$ (since $m_{2}(K_{t})$ works out to be $(t+1)/2$). Thus, there is quite a significant gap. The full conjecture has also been proved to be a consequence of the so-called KŁR conjecture of Kohayakawa, Łuczak and Rödl. This conjecture, regarding the number of $H$-free graphs of a certain type, remains open, except in a few special cases . The full KŁR conjecture was subsequently established by Balogh, Morris and Samotij and by Saxton and Thomason (see also ). Their methods also allow one to give alternative proofs for many of the results in this paper. We refer the reader to for a more complete overview.

As noted in , the KŁR conjecture would also imply the following structural result about $H$-free graphs which contain nearly the extremal number of edges. The analogous result in the dense case, due to Simonovits , is known as the stability theorem. Roughly speaking, it says that if an $H$-free graph contains almost $\left(1-\frac{1}{\chi(H)-1}\right)\binom{n}{2}$ edges, then it must be very close to being $(\chi(H)-1)$-partite.

Let $H$ be a graph with $\chi(H)\geq 3$ and let

Then, for every $\delta>0$, there exist positive constants $\epsilon$ and $C$ such that if $G$ is a random graph on $n$ vertices, where each edge is chosen independently with probability $p$ at least $Cn^{-1/m_{2}(H)}$, then, with probability tending to 1 as $n$ tends to infinity, every $H$-free subgraph of $G$ with at least $\left(1-\frac{1}{\chi(H)-1}-\epsilon\right)e(G)$ edges may be made $(\chi(H)-1)$-partite by removing at most $\delta pn^{2}$ edges.

Another example where some success has been achieved is Szemerédi’s theorem . This celebrated theorem states that, for every positive real number $\delta$ and every natural number $k$, there exists a positive integer $n$ such that every subset of the set $[n]=\{1,2,\cdots,n\}$ of size at least $\delta n$ contains a $k$-term arithmetic progression. The particular case where $k=3$ had been proved much earlier by Roth , and is accordingly known as Roth’s theorem. A sparse random version of Roth’s theorem was proved by Kohayakawa, Łuczak and Rödl . To state the theorem, let us say that a subset $I$ of the integers is $\delta$-Roth if every subset of $I$ of size $\delta|I|$ contains a $3$-term arithmetic progression. We shall also write $[n]_{p}$ for a random set in which each element of $[n]$ is chosen independently with probability $p$.

For every $\delta>0$ there exist positive constants $c$ and $C$ such that

Once again the 0-statement is trivial (as it tends to be for density theorems): if $p=n^{-1/2}/2$, then the expected number of $3$-term progressions in $[n]_{p}$ is less than $n^{1/2}/8$, while the expected number of elements of $[n]_{p}$ is $n^{1/2}/2$. Therefore, one can almost always remove an element from each progression and still be left with at least half the elements of $[n]_{p}$.

For longer progressions, the situation has been much less satisfactory. Let us define a set $I$ of integers to be $(\delta,k)$-Szemerédi if every subset of $I$ of cardinality at least $\delta|I|$ contains a $k$-term arithmetic progression. Until recently, hardly anything was known at all about which random sets were $(\delta,k)$-Szemerédi. However, that changed with the seminal paper of Green and Tao , who, on the way to proving that the primes contain arbitrarily long arithmetic progressions, showed that every pseudorandom set is $(\delta,k)$-Szemerédi, if “pseudorandom” is defined in an appropriate way. Their definition of pseudorandomness is somewhat complicated, but it is straightforward to show that quite sparse random sets are pseudorandom in their sense. From this the following result follows, though we are not sure whether it has appeared explicitly in print.

The approach of Green and Tao depends heavily on the use of a set of norms known as uniformity norms, introduced in . In order to deal with $k$-term arithmetic progressions, one must use a uniformity norm that is based on a count of certain configurations that can be thought of as $(k-1)$-dimensional parallelepipeds. These configurations have $k$ degrees of freedom (one for each dimension and one because the parallelepipeds can be translated) and size $2^{k-1}$. A simple argument (similar to the arguments for the 0-statements in the density theorems above) shows that the best bound that one can hope to obtain by their methods is therefore at most $p=n^{-k/2^{k-1}}$. This is far larger than the bound that arises in the obvious 0-statement for Szemerédi’s theorem: the same argument that gives a bound of $cn^{-1/2}$ for the Roth property gives a bound of $cn^{-1/(k-1)}$ for the Szemerédi property. However, even $p=n^{-k/2^{k-1}}$ is not the bound that they actually obtain, because they need in addition a “correlation condition” that is not guaranteed by the smallness of the uniformity norm. This means that the bound they obtain is of the form $n^{-o(1)}$.

The natural conjecture is that the obvious bound for the 0-statement is in fact correct, so it is far stronger than the bound of Green and Tao.

For every $\delta>0$ and every positive integer $k\geq 3$, there exist positive constants $c$ and $C$ such that

One approach to proving Szemerédi’s theorem is known as the hypergraph removal lemma. Proved independently by Nagle, Rödl, Schacht and Skokan and by the second author (see also ), this theorem states that for every $\delta>0$ and every positive integer $k\geq 2$ there exists a constant $\epsilon>0$ such that if $G$ is a $k$-uniform hypergraph containing at most $\epsilon n^{k+1}$ copies of the complete $k$-uniform hypergraph $K_{k+1}^{(k)}$ on $k+1$ vertices, then it may be made $K_{k+1}^{(k)}$-free by removing at most $\delta n^{k}$ edges. Once this theorem is known, Szemerédi’s theorem follows as an easy consequence. The question of whether an analogous result holds within random hypergraphs was posed by Łuczak . For $k=2$, this follows from the work of Kohayakawa, Łuczak and Rödl .

For every $\delta>0$ and every integer $k\geq 2$ there exist constants $\epsilon>0$ and $C$ such that, if $H$ is a random $k$-uniform hypergraph on $n$ vertices where each edge is chosen independently with probability $p$ at least $Cn^{-1/k}$, then, with probability tending to 1 as $n$ tends to infinity, every subgraph of $H$ containing at most $\epsilon p^{k+1}n^{k+1}$ copies of the complete $k$-uniform hypergraph $K_{k+1}^{(k)}$ on $k+1$ vertices may be made $K_{k+1}^{(k)}$-free by removing at most $\delta pn^{k}$ edges.

In the next few sections we shall give a very general method for proving sparse random versions of combinatorial theorems. This method allows one to obtain sharp bounds for several theorems, of which the principal (but by no means only) examples are positive answers to the conjectures we have just mentioned. This statement comes with one caveat. When dealing with graphs and hypergraphs, we shall restrict our attention to those which are well-balanced in the following sense. Note that most graphs of interest, including complete graphs and cycles, satisfy this condition.

A $k$-uniform hypergraph $K$ is said to be strictly $k$-balanced if, for every subgraph $L$ of $K$,

The main results we shall prove in this paper (in the order in which we discussed them above, but not the order in which we shall prove them) are as follows. The first is a sparse random version of Ramsey’s theorem. Of course, as we have already mentioned, this is known: however, our theorem applies not just to graphs but to hypergraphs, where the problem was wide open apart from a few special cases . As we shall see, our methods apply just as easily to hypergraphs as they do to graphs. We write $G_{n,p}^{(k)}$ for a random $k$-uniform hypergraph on $n$ vertices, where each hyperedge is chosen independently with probability $p$. If $K$ is some fixed $k$-uniform hypergraph, we say that a hypergraph is $(K,r)$-Ramsey if every $r$-colouring of its edges contains a monochromatic copy of $K$.

Given a natural number $r$ and a strictly $k$-balanced $k$-uniform hypergraph $K$, there exists a positive constant $C$ such that

One problem that the results of this paper leave open is to establish a corresponding 0-statement for Theorem 1.9. The above bound is the threshold below which the number of copies of $K$ becomes less than the number of hyperedges, so the results for graphs make it highly plausible that the 0-statement holds when $p<cn^{-1/m_{k}(K)}$ for small enough $c$. However, the example of stars, for which the threshold is lower than expected, shows that we cannot take this result for granted.

We shall also prove Conjecture 1.2 for strictly 2-balanced graphs. In particular, it holds for complete graphs.

Given $\epsilon>0$ and a strictly 2-balanced graph $H$, there exists a positive constant $C$ such that

A slightly more careful application of our methods also allows us to prove its structural counterpart, Conjecture 1.3, for strictly $2$-balanced graphs.

Given a strictly $2$-balanced graph $H$ with $\chi(H)\geq 3$ and a constant $\delta>0$, there exist positive constants $C$ and $\epsilon$ such that in the random graph $G_{n,p}$ chosen with probability $p\geq Cn^{-1/m_{2}(H)}$, where $m_{2}(H)=(e_{H}-1)/(v_{H}-2)$, the following holds with probability tending to 1 as $n$ tends to infinity. Every $H$-free subgraph of $G_{n,p}$ with at least $\left(1-\frac{1}{\chi(H)-1}-\epsilon\right)e(G)$ edges may be made $(\chi(H)-1)$-partite by removing at most $\delta pn^{2}$ edges.

We also prove Conjecture 1.6, obtaining bounds for the Szemerédi property that are essentially best possible.

Given $\delta>0$ and a natural number $k\geq 3$, there exists a constant $C$ such that

Our final main result is a proof of Conjecture 1.7, the sparse hypergraph removal lemma. As we have mentioned, the dense hypergraph removal lemma implies Szemerédi’s theorem, but it turns out that the sparse hypergraph removal lemma does not imply Theorem 1.12. The difficulty is this. When we prove Szemerédi’s theorem using the removal lemma, we first pass to a hypergraph to which the removal lemma can be applied. Unfortunately, in the sparse case, passing from the sparse random set to the corresponding hypergraph gives us a sparse hypergraph with dependencies between its edges, whereas in the sparse hypergraph removal lemma we assume that the edges of the sparse random hypergraph are independent. While it is likely that this problem can be overcome, we did not, in the light of Theorem 1.12, see a strong reason for doing so.

In addition to these main results, we shall discuss other density theorems, such as Turán’s theorem for hypergraphs (where, even though the correct bounds are not known in the dense case, we can obtain the threshold at which the bounds in the sparse random case will be the same), the multidimensional Szemerédi theorem of Furstenberg and Katznelson and the Bergelson-Leibman theorem concerning polynomial configurations in dense sets. In the colouring case, we shall discuss Schur’s theorem as a further example. Note that many similar results have also been obtained by a different method by Schacht and by Friedgut, Rödl and Schacht .

2 A preliminary description of the argument

The basic idea behind our proof is to use a transference principle to deduce sparse random versions of density and colouring results from their dense counterparts. To oversimplify slightly, a transference principle in this context is a statement along the following lines. Let $X$ be a structure such as the complete graph $K_{n}$ or the set $\{1,2,\dots,n\}$, and let $U$ be a sparse random subset of $X$. Then, for every subset $A\subset U$, there is a subset $B\subset X$ that has similar properties to $A$. In particular, the density of $B$ is approximately the same as the relative density of $A$ in $U$, and the number of substructures of a given kind in $A$ is an appropriate multiple of the number of substructures of the same kind in $B$.

Given a strong enough principle of this kind, one can prove a sparse random version of Szemerédi’s theorem, say, as follows. Let $A$ be a subset of $[n]_{p}$ of relative density $\delta$. Then there exists a subset $B$ of $[n]$ of size approximately $\delta n$ such that the number of $k$-term progressions in $B$ is approximately $p^{-k}$ times the number of $k$-term progressions in $A$. From Szemerédi’s theorem it can be deduced that the number of $k$-term progressions in $B$ is at least $c(\delta)n^{2}$, so the number of $k$-term progressions in $A$ is at least $c(\delta)p^{k}n^{2}/2$. Since the size of $A$ is about $pn$, we have roughly $pn$ degenerate progressions. Hence, there are non-degenerate progressions within $A$ as long as $p^{k}n^{2}$ is significantly larger than $pn$, that is, as long as $p$ is at least $Cn^{-1/(k-1)}$ for some large $C$.

It is very important to the success of the above argument that a dense subset of $[n]$ should contain not just one progression but several, where “several” means a number that is within a constant of the trivial upper bound of $n^{2}$. The other combinatorial theorems discussed above have similarly “robust” versions and again these are essential to us. Very roughly, our general theorems say that a typical combinatorial theorem that is robust in this sense will have a sparse random version with an upper bound for the probability threshold that is very close to a natural lower bound that is trivial for density theorems and often true, even if no longer trivial, for Ramsey theorems.

The idea of using a transference principle to obtain sparse random versions of robust combinatorial statements is not what is new about this paper. In fact, this was exactly the strategy of Green and Tao in their paper on the primes, and could be said to be the main idea behind their proof (though of course it took many further ideas to get it to work). Since it is difficult to say what is new about our argument without going into slightly more detail, we postpone further discussion for now. However, there are three further main ideas involved and we shall highlight them as they appear.

In the next few sections, we shall find a very general set of criteria under which one may transfer combinatorial statements to the sparse random setting. In Sections 5-8, we shall show how to prove that these criteria hold. Section 9 is a brief summary of the general results, both conditional and unconditional, that have been proved up to that point. In Section 10, we show how these results may be applied to prove the various theorems promised in the introduction. In Section 11, we conclude by briefly mentioning some questions that are still open.

3 Notation

Often our set $U$ will be a random subset of $X$ with each element of $X$ chosen with probability $p$, the choices being independent. In this case, we shall use the shorthand $U=X_{p}$, just as we wrote $[n]_{p}$ for a random subset of $[n]$ in the statement of the sparse random version of Szemerédi’s theorem earlier. When $U=X_{p}$ it is more convenient to consider the measure $\mu$ that is equal to $p^{-1}$ times the characteristic function of $U$. That is, $\mu(x)=p^{-1}$ if $x\in U$ and 0 otherwise. To avoid confusion, we shall call this the associated measure of $U$. Strictly speaking, we should not say this, since it depends not just on $U$ but on the value of $p$ used when $U$ was chosen, but this will always be clear from the context so we shall not bother to call it the associated measure of $(U,p)$.

It follows trivially from this definition that $|\langle f,\phi\rangle|\leq\|f\|\|\phi\|^{*}$. Almost as trivially, it follows that if $|\langle f,\phi\rangle|\leq 1$ whenever $\|f\|\leq\eta$, then $\|\phi\|^{*}\leq\eta^{-1}$, a fact that will be used repeatedly.

Transference principles

As we have already mentioned, a central notion in this paper is that of transference. Roughly speaking, a transference principle is a theorem that states that every function $f$ in one class can be replaced by a function $g$ in another, more convenient class in such a way that the properties of $f$ and $g$ are similar.

To understand this concept and why it is useful, let us look at the sparse random version of Szemerédi’s theorem that we shall prove. Instead of attacking this directly, it is convenient to prove a functional generalization of it. The statement we shall prove is the following.

In the rest of this section we shall show how the Hahn-Banach theorem can be used to prove general transference principles. This was first demonstrated by the second author in , and independently (in a slightly different language) by Reingold, Trevisan, Tulsiani and Vadhan , and leads to simpler proofs than the method used by Green and Tao. The first transference principle we shall prove is particularly appropriate for density theorems: this one was shown in but for convenience we repeat the proof. Then we shall prove a modification of it for use with colouring theorems.

Let us begin by stating the finite-dimensional Hahn-Banach theorem in its separation version.

By Lemma 2.3 there is a function $\phi$ and a real number $t$ such that $\langle f,\phi\rangle>t$ and such that $\langle g+h,\phi\rangle\leq t$ whenever $g\in K$ and $h\in L$. Setting $h=0$ we deduce that $\langle g,\phi\rangle\leq t$ for every $g\in K$, and setting $g=0$ we deduce that $\langle h,\phi\rangle\leq t$ for every $h\in L$. Setting $g=h=0$ we deduce that $t\geq 0$. Dividing through by $t$ (or by $\frac{1}{2}\langle f,\phi\rangle$ if $t=0$) we see that we may take $t$ to be 1. $\Box$

Now let us prove our two transference principles, beginning with the density one. In the statement of the theorem below we write $\phi_{+}$ for the positive part of $\phi$.

If we cannot approximate $(1+\epsilon)^{-1}f$ in this way, then we cannot write $(1+\epsilon)^{-1}f$ as a sum $g+h$ with $0\leq g\leq\nu$ and $\|h\|\leq\eta$. Now the sets $K=\{g:0\leq g\leq\nu\}$ and $L=\{h:\|h\|\leq\eta\}$ are closed and convex and they both contain 0. It follows from Lemma 2.4, with $Y=X$, that there is a function $\phi$ with the following three properties.

$\langle(1+\epsilon)^{-1}f,\phi\rangle>1$;

$\langle g,\phi\rangle\leq 1$ whenever $0\leq g\leq\nu$;

$\langle h,\phi\rangle\leq 1$ whenever $\|h\|\leq\eta$.

From the first of these properties we deduce that $\langle f,\phi\rangle>1+\epsilon$. From the second we deduce that $\langle\nu,\phi_{+}\rangle\leq 1$, since the function $g$ that takes the value $\nu(x)$ when $\phi(x)\geq 0$ and $0$ otherwise maximizes the value of $\langle g,\phi\rangle$ over all $g\in K$. And from the third property we deduce immediately that $\|\phi\|^{*}\leq\eta^{-1}$.

But our hypothesis implies that $\langle\mu,\phi_{+}\rangle\leq\langle\nu,\phi_{+}\rangle+\epsilon$. It therefore follows that

Later we shall apply Lemma 2.5 with $\mu$ the associated measure of a sparse random set and $\nu$ the constant measure 1.

The next transference principle is the one that we shall use for obtaining sparse random colouring theorems. It may seem strange that the condition we obtain on $g_{1}+\dots+g_{r}$ is merely that it is less than $\nu$ (rather than equal to $\nu$). However, we also show that $f_{i}$ and $g_{i}$ are close in a certain sense, and in applications that will imply that $g_{1}+\dots+g_{r}$ is indeed approximately equal to $\nu$ (which will be the constant measure 1). With a bit more effort, one could obtain equality from the Hahn-Banach method, but this would not make life easier later, since the robust versions of Ramsey theorems hold just as well when you colour almost everything as they do when you colour everything.

Suppose that the result does not hold for the $r$-tuple $(f_{1},\dots,f_{r})$. Let $K$ be the closed convex set of all $r$-tuples of functions $(g_{1},\dots,g_{r})$ such that $g_{i}\geq 0$ for each $i$ and $g_{1}+\dots+g_{r}\leq\nu$, and let $L$ be the closed convex set of all $r$-tuples $(h_{1},\dots,h_{r})$ such that $\|h_{i}\|\leq\eta$ for each $i$. Then both $K$ and $L$ contain 0 and our hypothesis is that $(1+\epsilon)^{-1}(f_{1},\dots,f_{r})\notin K+L$. Therefore, Lemma 2.4, with $Y=X^{r}$, gives us an $r$-tuple of functions $(\phi_{1},\dots,\phi_{r})$ with the following three properties.

$\sum_{i=1}^{r}\langle(1+\epsilon)^{-1}f_{i},\phi_{i}\rangle>1$;

$\sum_{i=1}^{r}\langle g_{i},\phi_{i}\rangle\leq 1$ whenever $g_{i}\geq 0$ for each $i$ and $g_{1}+\dots+g_{r}\leq\nu$;

$\sum_{i=1}^{r}\langle h_{i},\phi_{i}\rangle\leq 1$ whenever $\|h_{i}\|\leq\eta$ for each $i$.

The first of these conditions implies that $\sum_{i=1}^{r}\langle f_{i},\phi_{i}\rangle>1+\epsilon$. In the second condition, let us choose the functions $g_{i}$ as follows. For each $x$, pick an $i$ such that $\phi_{i}(x)$ is maximal. If $\phi_{i}(x)\geq 0$, then set $g_{i}(x)$ to be $\nu(x)$, and otherwise set $g_{i}(x)=0$. For each $j\neq i$, set $g_{j}(x)$ to be zero. Then $\sum_{i=1}^{r}g_{i}(x)\phi_{i}(x)$ is equal to $\nu(x)\max_{i}\phi_{i}(x)$ if this maximum is non-negative, and 0 otherwise. Therefore, $\sum_{i=1}^{r}\langle g_{i},\phi_{i}\rangle=\langle\nu,(\max_{i}\phi_{i})_{+}\rangle$. Thus, it follows from the second condition that $\langle\nu,(\max_{i}\phi_{i})_{+}\rangle\leq 1$. Let us write $\phi$ for $\max_{i}\phi_{i}$. The third condition implies that $\|\phi_{i}\|^{*}\leq\eta^{-1}$ for each $i$.

Using this information together with our hypothesis about $\mu-\nu$, we find that

The counting lemma

We now come to the second main idea of the paper, and perhaps the main new idea. Lemmas 2.5 and 2.6 will be very useful to us, but as they stand they are rather abstract: in order to make use of them we need to find a norm $\|.\|$ such that if $\|f-g\|$ is small then $f$ and $g$ behave similarly in a relevant way. Several norms have been devised for exactly this purpose, such as the uniformity norms mentioned earlier, and also “box norms” for multidimensional structures and “octahedral norms” for graphs and hypergraphs. It might therefore seem natural to try to apply Lemmas 2.5 and 2.6 to these norms. However, as we have already commented in the case of uniformity norms, if we do this then we cannot obtain sharp bounds: except in a few cases, these norms are related to counts of configurations that are too large to appear non-degenerately in very sparse random sets.

We are therefore forced to adopt a different approach. Instead of trying to use an off-the-shelf norm, we use a bespoke norm, designed to fit perfectly the problem at hand. Notice that Lemmas 2.5 and 2.6 become harder to apply as the norm $\|.\|$ gets bigger, since then the dual norm $\|.\|^{*}$ gets smaller and there are more functions $\phi$ with $\|\phi\|^{*}\leq\eta^{-1}$, and therefore more functions of the form $\phi_{+}$ for which one must show that $\langle\mu-\nu,\phi_{+}\rangle\leq\epsilon$ (and similarly for $(\max_{1\leq i\leq r}\phi_{i})_{+}$ with colouring problems). Therefore, we shall try to make our norm as small as possible, subject to the condition we need it to satisfy: that $f$ and $g$ behave similarly if $\|f-g\|$ is small.

Thus, our norm will be defined by means of a universal construction. As with other universal constructions, this makes the norm easy to define but hard to understand concretely. However, we can get away with surprisingly little understanding of its detailed behaviour, as will become clear later. An advantage of this abstract approach is that it has very little dependence on the particular problem that is being studied: it is for that reason that we have ended up with a very general result.

Before we define the norm, let us describe the general set-up that we shall analyse. We shall begin with a finite set $X$ and a collection $S$ of ordered subsets of $X$, each of size $k$. Thus, any element $s\in S$ may be expressed in the form $s=(s_{1},\dots,s_{k})$.

In both these two examples, the collection $S$ of ordered subsets of $X$ has some nice homogeneity properties, which we shall assume for our general result because it makes the proofs cleaner, even if one sometimes has to work a little to show that these properties may be assumed.

Let $S$ be a collection of ordered $k$-tuples $s=(s_{1},\dots,s_{k})$ of elements of a finite set $X$, and let us write $S_{j}(x)$ for the set of all $s$ in $S$ such that $s_{j}=x$. We shall say that $S$ is homogeneous if for each $j$ the sets $S_{j}(x)$ all have the same size.

The functional version of a combinatorial theorem about the ordered sets in $S$ will involve expressions such as

Thus, what we wish to do is define a norm $\|.\|$ with the property that

can be bounded above in terms of $\|f-g\|$ whenever $0\leq f\leq\mu$ and $0\leq g\leq\nu$. This is what we mean by saying that $f$ and $g$ should behave similarly when $\|f-g\|$ is small.

It will be very convenient to introduce some terminology and notation for expressions of the kind that are beginning to appear.

as $\langle f-g,*_{j}(g\dots,g,f,\dots,f)\rangle$ (where it is understood that there are $j-1$ occurrences of $g$ and $k-j$ occurrences of $f$), and from that we obtain the identity

This, together with the triangle inequality, gives us the following lemma.

Let $X$ be a finite set and let $S$ be a homogeneous collection of ordered subsets of $X$, each of size $k$. Let $f$ and $g$ be two functions defined on $X$. Then

Any convolution $*_{j}(g,\dots,g,f,\dots,f)$ is bounded above by $*_{j}(\nu,\dots,\nu,\mu,\dots,\mu)$. For the sake of example, let us consider the case of Szemerédi’s theorem. Taking $\nu=1$, we see that the $j$th convolution is bounded above by the function

Up to normalization, this counts the number of progressions of length $k-j+1$ beginning at $x$. If $j>1$, probabilistic estimates imply that, at the critical probability $p=Cn^{-1/(k-1)}$, $P_{j}$ is, with high probability, $L_{\infty}$-bounded (that is, the largest value of the function is bounded by some absolute constant). However, functions of the form $*_{1}(f,\dots,f)$ with $0\leq f\leq\mu$ are almost always unbounded. This makes it much more difficult to control their inner products with $\mu-1$, and we need to do that if we wish to apply the abstract transference principle from the previous section.

For graphs, a similar problem arises. The $j$th convolution will count, up to normalization, the number of copies of some subgraph of the given graph $H$ that are rooted on a particular edge. If we assume that the graph is balanced, as we are doing, then, at probability $p=Cn^{-1/m_{2}(H)}$, this count will be $L_{\infty}$-bounded for any proper subgraph of $H$. However, for $H$ itself, we do not have this luxury and the function $*_{1}(f,\dots,f)$ is again likely to be unbounded.

If we were prepared to increase the density of the random set by a polylogarithmic factor, we could ensure that even $*_{1}(f,\dots,f)$ was bounded and this problem would go away. Thus, a significant part of the complication of this paper is due to our wish to get a bound that is best possible up to a constant.

There are two natural ways of getting around the difficulty if we are not prepared to sacrifice a polylogarithmic factor. One is to try to exploit the fact that although $*_{1}(f,\dots,f)$ is not bounded, it typically takes large values very infrequently, so it is “close to bounded” in a certain sense. The other is to replace $*_{1}(f,\dots,f)$ by a modification of the function that has been truncated at a certain maximum. It seems likely that both approaches can be made to work: we have found it technically easier to go for the second. The relevant definition is as follows.

A natural quantity that fits this description is $\langle f,\circ_{1}(f,f,\dots,f)\rangle$, and this is indeed closely related to the quantity we shall actually consider. However, there is an additional complication, which is that it is very convenient to think of our random set $U$ as a union of $m$ random sets $U_{1},\dots,U_{m}$, and of a function defined on $U$ as an average $m^{-1}(f_{1}+\dots+f_{m})$ of functions with $f_{i}$ defined on $U_{i}$. More precisely, we shall take $m$ independent random sets $U_{1},\dots,U_{m}$, each distributed as $X_{p}$. (Recall that $X_{p}$ stands for a random subset of $X$ where the elements are chosen independently with probability $p$.) Writing $\mu_{1},\dots,\mu_{m}$ for their associated measures, for each $i$ we shall take a function $f_{i}$ such that $0\leq f_{i}\leq\mu_{i}$. Our assertion will then be about the average $f=m^{-1}(f_{1}+\dots+f_{m})$. Note that $0\leq f\leq\mu$, where $\mu=m^{-1}(\mu_{1}+\dots+\mu_{m})$, and that every function $f$ with $0\leq f\leq\mu$ can be expressed as an average of functions $f_{i}$ with $0\leq f_{i}\leq\mu_{i}$. Note also that if $U=U_{1}\cup\dots\cup U_{m}$ then $\mu$ is neither the characteristic measure of $U$ nor the associated measure of $U$. However, provided $p$ is fairly small, it is close to both with high probability, and this is all that matters.

Having chosen $f$ in this way, the quantity we shall then look at is

In other words, we expand the expression $\langle f,*_{1}(f,f,\dots,f)\rangle$ in terms of $f_{1},\dots,f_{m}$ and then do the capping term by term.

Central to our approach is a “counting lemma”, which is an easy corollary of the following result, which keeps track of the errors that are introduced by our “capping”. (To understand the statement, observe that if we replaced the capped convolutions $\circ_{j}$ by their “genuine” counterparts $*_{j}$, then the two quantities that we are comparing would become equal.) In the next lemma, we assume that a homogeneous set $S$ of ordered $k$-tuples has been given.

Since $0\leq*_{1}(f_{i_{2}},\dots,f_{i_{k}})\leq*_{1}(\mu_{i_{2}},\dots,\mu_{i_{k}})$, our assumption implies that, whenever $i_{2},\dots,i_{k}$ are distinct, $\|*_{1}(f_{i_{2}},\dots,f_{i_{k}})-\circ_{1}(f_{i_{2}},\dots,f_{i_{k}})\|_{1}\leq\eta$. In this case, therefore,

We also know that $\langle g,*_{1}(f_{i_{2}},\dots,f_{i_{k}})\rangle=\langle f_{i_{2}},*_{2}(g,f_{i_{3}},\dots,f_{i_{k}})\rangle$ and that if $i_{3},\dots,i_{k}$ are distinct then $*_{2}(g,f_{i_{3}},\dots,f_{i_{k}})=\circ_{2}(g,f_{i_{3}},\dots,f_{i_{k}})$. Therefore,

Now the assumption that $*_{j}(1,1,\dots,1,\mu_{i_{j+1}},\dots,\mu_{i_{k}})$ is bounded above by 2 whenever $j\geq 2$ and $i_{j+1},\dots,i_{k}$ are distinct implies that $\circ_{j}(g,g,\dots,g,f_{i_{j+1}},\dots,f_{i_{k}})$ and $*_{j}(g,g,\dots,g,f_{i_{j+1}},\dots,f_{i_{k}})$ are equal under these circumstances. From this it is a small exercise to show that

Therefore, for $i_{2},\dots,i_{k}$ distinct,

The probability that $i_{1},\dots,i_{k}$ are not distinct is at most $\binom{k}{2}m^{-1}\leq\eta/4k$, and if they are not distinct then the difference between (1) and (2) is certainly no more than $4k$ (since all capped convolutions take values in $$and$\|f_{i_{j}}\|_{1}\leq\|\mu_{i_{j}}\|_{1}\leq 2$). Therefore, taking the expectation over all$(i_{1},\dots,i_{k})$(not necessarily distinct) and noting that$\langle g,\circ_{k}(g,g,\dots,g)\rangle=\langle g,*_{1}(g,g,\dots,g)\rangle$, we find that

To state our counting lemma, we need to define the norm that we shall actually use.

Let $X$ be a finite set and let $S$ be a homogeneous collection of ordered subsets of $X$, each of size $k$. Let $\mu=(\mu_{1},\dots,\mu_{m})$ be a sequence of measures on $X$. A $(\mu,1)$-basic anti-uniform function is a function of the form $\circ_{j}(g,\dots,g,f_{i_{j+1}},\dots,f_{i_{k}})$, where $1\leq j\leq k$, $i_{j+1},\dots,i_{k}$ are distinct, $0\leq g\leq 1$ and $0\leq f_{i_{h}}\leq\mu_{i_{h}}$ for every $h$ between $j+1$ and $k$. Let $\Phi_{\mu,1}$ be the set of all $(\mu,1)$-basic anti-uniform functions and define the norm $\|.\|_{\mu,1}$ by taking $\|h\|_{\mu,1}$ to be $\max\{|\langle h,\phi\rangle|:\phi\in\Phi_{\mu,1}\}$.

The phrase “basic anti-uniform function” is borrowed from Green and Tao, since our basic anti-uniform functions are closely related to functions of the same name that appear in their paper .

Now the probability that $i_{1},\dots,i_{k}$ are distinct is again at most $\eta/4k$, and if they are not distinct we at least know that $|\langle f-g,\circ_{j}(g,g,\dots,g,f_{i_{j+1}},\dots,f_{i_{k}})\rangle|\leq 4$. Therefore, our hypothesis also implies that

Combining this with Lemma 3.5, we obtain the result. $\Box$

In order to prove analogues of structural results such as the Erdős-Simonovits stability theorem and the hypergraph removal lemma we shall need to preserve slightly more information when we replace our sparsely supported function $f$ by a densely supported function $g$. For example, to prove the stability theorem, we proceed as follows. Given a subgraph $A$ of the random graph $G_{n,p}$, we create a weighted subgraph $B$ of $K_{n}$ that contains the same number of copies of $H$, up to normalization. However, to make the proof work, we also need the edge density of $B$ within any large vertex set to correspond to the edge density of $A$ within that set. Suppose that we have this property as well and that $A$ is $H$-free. Then $B$ has very few copies of $H$. A robust version of the stability theorem then tells us that $B$ may be made $(\chi(H)-1)$-partite by removing a small number of edges (or rather a small weight of weighted edges). Let us look at the resulting weighted graph $B^{\prime}$. It consists of $\chi(H)-1$ vertex sets, all of which have zero weight inside. Therefore, in $B$, each of these sets had only a small weight to begin with. Since all “local densities” of $A$ reflect those of $B$, these vertex sets contain only a very small proportion of the edges in $A$ as well. Removing these edges makes $A$ into a $(\chi(H)-1)$-partite graph and we are done.

How do we ensure that local densities are preserved? All we have to do is enrich our set of basic anti-uniform functions by adding an appropriate set of functions that will allow us to transfer local densities from the sparse structure to the dense one. For example, in the case above we need to know that $A$ and $B$ have roughly the same inner product (when appropriately weighted) with the characteristic function of the complete graph on any large set $V$ of vertices. We therefore add these characteristic functions to our stock of basic anti-uniform functions. For other applications, we need to maintain more intricate local density conditions. However, as we shall see, as long as the corresponding set of additional functions is sufficiently small, this does not pose a problem.

A conditional proof of the main theorems

In this section, we shall collect together the results of Sections 2 and 3 in order to make clear what is left to prove. We start with a simple and general lemma about duality in normed spaces.

If $\psi=\sum_{i}\lambda_{i}\phi_{i}$ with $\phi_{i}\in\Phi\cup(-\Phi)$, $\lambda_{i}\geq 0$ for each $i$ and $\sum_{i}\lambda_{i}=1$, and if $\|f\|\leq 1$, then $|\langle f,\psi\rangle|\leq\sum_{i}\lambda_{i}|\langle f,\phi_{i}\rangle|\leq 1$. The same is then true if $\psi$ belongs to the closure of the convex hull of $\Phi\cup(-\Phi)$.

If $\psi$ does not belong to this closed convex hull, then by the Hahn-Banach theorem there must be a function $f$ such that $|\langle f,\phi\rangle|\leq 1$ for every $\phi\in\Phi$ and $\langle f,\psi\rangle>1$. The first condition tells us that $\|f\|\leq 1$, so the second implies that $\|\psi\|^{*}>1$. $\Box$

So we already know a great deal about functions $\phi$ with bounded dual norm. Recall, however, that we must consider positive parts of such functions: we would like to show that $\langle\mu-\nu,\phi_{+}\rangle$ is small whenever $\|\phi\|^{*}$ is of reasonable size. We need the following extra lemma to gain some control over these.

Let $\Psi$ be a set of functions that take values in $$and let$\epsilon>0$. Then there exist constants$d$and$M$, depending on$\epsilon$only, such that for every function$\psi$in the convex hull of$\Psi$, there is a function$\omega$that belongs to$M$times the convex hull of all products$\pm\phi_{1}\dots\phi_{j}$with$j\leq d$and$\phi_{1},\dots,\phi_{j}\in\Psi$, such that$\|\psi_{+}-\omega\|_{\infty}<\epsilon$.

We start with the well-known fact that continuous functions on closed bounded intervals can be uniformly approximated by polynomials. Therefore, if $K(x)$ is the function defined on $$that takes the value$0$if$x\leq 0$and$x$if$x\geq 0$, then there is a polynomial$P$such that$|P(x)-K(x)|\leq\epsilon$for every$x\in$. It follows that if$\psi$is a function that takes values in$$, then$\|P(\psi)-\psi_{+}\|_{\infty}\leq\epsilon$.

Let us apply this observation in the case where $\psi$ is a convex combination $\sum_{i}\lambda_{i}\phi_{i}$ of functions $\phi_{i}\in\Psi$. If $P(t)=\sum_{j=1}^{d}a_{j}t^{j}$, then

But $\sum_{i_{1},\dots,i_{j}}\lambda_{i_{1}}\dots\lambda_{i_{j}}=1$ for every $j$, so this proves that we can take $M$ to be $\sum_{j=1}^{d}|a_{j}|$. This bound and the degree $d$ depend on $\epsilon$ only, as claimed. $\Box$

Similarly, for colouring problems, where we need to deal with the function $(\max_{1\leq i\leq r}\phi_{i})_{+}$, we have the following lemma. The proof is very similar to that of Lemma 4.2, though we must replace the function $K(x)$ that has to be approximated with the function $K(x_{1},\dots,x_{r})=\max\{0,x_{1},\dots,x_{r}\}$ and apply a multivariate version of the uniform approximation theorem inside the set $^{r}$ (though the case we actually need follows easily from the one-dimensional theorem).

Let $\Psi$ be a set of functions that take values in $$and let$\epsilon>0$. Then there exist constants$d$and$M$, depending on$\epsilon$only, such that for every set of functions$\psi_{1},\dots,\psi_{r}$in the convex hull of$\Psi$, there is a function$\omega$that belongs to$M$times the convex hull of all products$\pm\phi_{1}\dots\phi_{j}$with$j\leq d$and$\phi_{1},\dots,\phi_{j}\in\Psi$, such that$\|(\max_{1\leq i\leq r}\psi_{i})_{+}-\omega\|_{\infty}<\epsilon$.$\square$

We shall split up the rest of the proof of our main result as follows. First, we shall state a set of assumptions about the set $S$ of ordered subsets of $X$. Then we shall show how the transference results we are aiming for follow from these assumptions. Then over the next few sections we shall show how to prove these assumptions for a large class of sets $S$.

The reason for doing things this way is twofold. First, it splits the proof into a deterministic part (the part we do now) and a probabilistic part (verifying the assumptions). Secondly, it splits the proof into a part that is completely general (again, the part we do now) and a part that depends more on the specific set $S$. Having said that, when it comes to verifying the assumptions, we do not do so for individual sets $S$. Rather, we identify two broad classes of set $S$ that between them cover all the problems that have traditionally interested people. This second shift, from the general to the particular, will not be necessary until Section 7. For now, the argument remains quite general.

Suppose now that $\mu_{1},\dots,\mu_{m}$ are measures on a finite set $X$ and $\mu=m^{-1}(\mu_{1}+\dots+\mu_{m})$. In subsequent sections, we will take $\mu_{1},\dots,\mu_{m}$ to be the associated measures of random sets $U_{1},\dots,U_{m}$, each distributed as $X_{p}$, but for now we will continue to work deterministically. We shall be particularly interested in the following four properties that such a sequence of measures may have.

$\|\mu_{i}\|_{1}=1+o(1)$ for each $i$, where $o(1)\rightarrow 0$ as $|X|\rightarrow\infty$.

$\|*_{1}(\mu_{i_{2}},\dots,\mu_{i_{k}})-\circ_{1}(\mu_{i_{2}},\dots,\mu_{i_{k}})\|_{1}\leq\eta$ whenever $i_{2},\dots,i_{k}$ are distinct integers between 1 and $m$.

$\|*_{j}(1,1,\dots,1,\mu_{i_{j+1}},\dots,\mu_{i_{k}})\|_{\infty}\leq 2$ whenever $j\geq 2$ and $i_{j+1},\dots,i_{k}$ are distinct integers between 1 and $m$.

$|\langle\mu-1,\xi\rangle|<\lambda$ whenever $\xi$ is a product of at most $d$ basic anti-uniform functions from $\Phi_{\mu,1}$.