The upper tail problem for induced 4-cycles in sparse random graphs

The study of the random variable counting the number of copies of a given graph in the binomial random graph $G_{n,p}$ has a very long history and many things are known about it. In particular, for every graph $H$, when the expected number of copies of $H$ in $G_{n,p}$ tends to infinity a ‘law of large numbers’, see Bollobás [6], and a central limit theorem are known, see Ruciński [28].

After establishing such results, it is natural to ask what is the probability of the event that this random variable differs from its expectation by a significant amount. In this paper, we will consider only the ‘upper tail’ problem: what is the probability of a random variable exceeding its expectation by a multiplicative factor $1+\delta$, where $\delta$ is some positive real.

We continue by recalling some definitions to make our discussion more rigorous. For every non-negative integer $n$ and a sequence $p=p(n)\in(0,1)$, we let $G_{n,p}$ be the binomial random graph with $n$ vertices and density $p$. Furthermore, for any graph $H$, let $X^{H}_{n,p}$ be the random variable counting the number of (labeled) copies of $H$ in $G_{n,p}$. Further, for any $\delta$ a positive real and a random variable $Y$ we write $\mathbf{UT}(Y,\delta)$ for the event $\{Y\geq(1+\delta)\mathbb{E}[Y]\}$.

The work on the problem of estimating (the logarithm of) the upper tail probability of $X_{n,p}^{H}$ was initiated by the famous works of Kim and Vu [24], Vu [29], Janson and Ruciński [23]. This problem turns out to be so difficult¹¹1This problem was called ‘the infamous upper tail’ by Janson and Ruciński [23]. because when $H$ is a connected graph with at least two edges $X_{n,p}^{H}$ is not a linear function of independent Bernoulli random variables. In the case of linear functions, life is easier and much is known about its large deviation properties, see [15].

In a famous paper [22], Janson, Oleszkiewicz, and Ruciński estimated the logarithm of the upper tail probability for every graph $H$ up to a multiplicative factor of $O(\log(1/p))$. Seven years later, Chatterjee [8] and DeMarco–Kahn [14] closed this gap up to a multiplicative factor of $O(1)$ when $H$ is a triangle and DeMarco–Kahn [13] generalized this for a clique of arbitrary size.

Next, one would like to obtain a first order approximation of the logarithm of the upper tail probability. The first to do that were Chatterjee and Varadhan [10]. They obtained a first order approximation of the upper tail probability for any graph, under the assumption that $p$ is a constant. Their proof relied on the regularity method and therefore extends only to $p$ tending to zero very slowly, for more discussion about this see [26].

The general strategy for estimating the logarithm of the upper tail probability, used by Chatterjee and Varadhan as well as all later works on this subject, is to establish a ‘large deviation principle’. That is to prove that the logarithm of the upper tail probability is asymptotically equal to the solution to a minimization problem over a non-trivial set of product probability measures. These minimization problems are called ‘variational problems’. After achieving such large deviation principle one is then left with solving the variational problem.

In a breakthrough paper of Chatterjee–Dembo [9], the authors established a ‘large deviation principle’ not only for $X_{n,p}^{H}$ when $p=\Omega(n^{-\varepsilon})$, but also for a large class of functions of $N$ independent Bernoulli random variables with mean $p=\Omega(N^{-\varepsilon})$. They proved that for any ‘smooth enough’ function $f\colon\{0,1\}^{N}\to\mathbb{R}$ and a sequence of independent Bernoulli random variables $Y=(Y_{1},Y_{2},\ldots,Y_{N})\in\{0,1\}^{N}$, all with mean $p$, we have the following:

where $I_{p}(q)=q\log\left(\frac{q}{p}\right)+(1-q)\log\left(\frac{1-q}{1-p}\right)$ is the relative entropy (the Kullback–Leibler divergence) between $\operatorname{Ber}(q)$ and $\operatorname{Ber}(p)$, and $\tilde{Y}=(\tilde{Y}_{1},\tilde{Y}_{2},\ldots,\tilde{Y}_{N})\in\{0,1\}^{N}$ is a sequence of independent Bernoulli random variables with $\mathbb{E}[\tilde{Y}_{i}]=q_{i}$ for each $i$.

This was further developed by Eldan [16] and Augeri [2, 3]. These methods are completely different from the ones used in the dense regime.

Revisiting the ideas from Chatergee–Varhadan [10], Cook–Dembo [11] developed a decomposition theorem similar to Szemerédi’s regularity lemma and a corresponding counting lemma which are suitable for sparse graphs. Using these they extended the range of sparsity of $p$ were the variational approximation (1) holds (for every graph $H$). Generalizing this method, Cook–Dembo–Pham [12] pushed the bounds even further in the case of subgraph count. They also obtained an approximation of the logarithm of the upper tail probability for the count of uniform sub-hypergraphs in the binomial random uniform hypergraph model, and the induced count of graphs in $G_{n,p}$. Their result combined with the solution to the corresponding variational problem for uniform hypergraph cliques, and one more non-trivial 3-uniform hypergraph which were given by Liu–Zhao in [25], yields estimations for the sub-hypergraph count in the binomial random hypergraph model in the sparse regime. We also note that to the best of our knowledge the solution to the ‘induced variational problem’ is not known apart from the case where $H$ is a clique. The case of the induced subgraph count will be of main interest in this paper, and will be discussed later.

To estimate the asymptotics of the logarithm of the upper tail probability, one also needs to solve the variational problem in the right-hand side of (1). In the case of the random variable $X_{n,p}^{H}$, Lubetzky and Zhao [27], and Bhattacharya, Ganguly, Lubetzky, and Zhao [5] solved this variational problem for all $H,n$ and $p$ satisfying $n^{-1/\Delta_{H}}\ll p\ll 1$. This then leads to a first order approximation of the logarithm of the upper tail probability for $X_{n,p}^{H}$ for every graph $H$ and $p\geq n^{-c_{H}}$. We wish to emphasize that, in all known cases, when $f$ counts the number of copies of a given $H$ in $G_{n,p}$, the solution to the corresponding variational problem (the right hand side of (1)) always satisfies $q_{i}\in\{p,1\}$ when $p=o(1)$.

A recent surprising result due to Gunby [20] studied the upper tail probability for subgraph counts in a random regular graph $G_{n,d}$, where he also proved a large deviation principle. However, for a particular graph, and certain range of $d$ (the regularity) the answer for this variational problem is achieved with three possible values of $q_{i}$ and not two as in the binomial random graph model.

In a breakthrough paper of Harel, Mousset and Samotij [21], using a combinatorial approach, the authors managed to extend the range where the variational problem (the same one as before) bounds from above the logarithm of the upper tail probability for the count of cliques to the optimal range of $p$, which is $p^{\frac{r-1}{2}}\gg n^{-1}(\log(n))^{\frac{1}{r-2}}$ for a clique on $r$ vertices²²2That is because below this threshold they also showed a Poisson approximation.. We wish to emphasize that their approach for solving the upper tail problem is completely different from any previous techniques in the papers mentioned above. This, together with the solution to the variational problem, settled the problem of the first order approximation of the logarithm of the upper tail probability for cliques. Moreover, they established the correct range of $p$, up to a polylogarithmic factor, where the variational problem bounds from above the logarithm of the upper tail probability for non-bipartite regular graphs³³3For bipartite regular graphs their result was not optimal, but also a lot of progress was made..

Building on the combinatorial ideas of Harel, Mousset and Samotij, Basak and Basu [4] extended the range of $p$ to the optimal range for all regular graphs, including bipartite graphs. Again, this with the solution to the variational problem settled the problem of estimating the logarithm of the upper tail probability for regular graphs. We summarize this discussion with the following first order approximation of the upper tail problem for regular graphs in the ‘localized regime’.

In this paper we estimate the logarithm of the upper tail probability for the count of induced copies of $C_{4}$ in $G_{n,p}$ in the range $\frac{\log^{9}(n)}{n}\ll p\ll 1$, which is optimal up to $\log^{9}(n)$ in the lower bound. To the best of our knowledge, this is the first exact result for the upper tail probability of a random variable counting the number of induced copies of a given non-complete graph in $G_{n,p}$. Our proofs rely heavily on the combinatorial approach of Harel, Mousset and Samotij.

We now present the main result of this paper. For this, from now on let $X$ be the random variable counting the number of induced copies of $C_{4}$ in $G_{n,p}$.

thmthebesttheorem There is an explicit sequence $0=c_{1}<c_{2}<\ldots\leq 1/3$ such that the following holds for $p\gg\frac{\log^{9}(n)}{n}$:

where $\rho_{k}(n,p)=\sqrt{\frac{k}{k-1}}\left(1-\frac{2}{k}+\frac{\log(n)}{k\log(p)}\right)<1$.

The sequence above is explicitly defined in Section 6.

There are several interesting phenomena which distinguish Theorem 1.1 from previous results concerning the upper tail problem for subgraph counts.

The first, and most noticeable difference is the infinite number of phase transitions. To the best of our knowledge, there is no earlier example of an upper tail problem exhibiting infinitely many phase transitions in its first order approximation. To understand the reasons for this phenomenon let us first discuss further Theorem 1.1. A strategy to bound from below the upper tail probability is to observe that, conditioned on the event $C\subseteq G_{n,p}$ for some $C$ satisfying $\mathbb{E}\left[X_{n,p}^{H}\mid C\subseteq G_{n,p}\right]\geq(1+\delta)\mathbb{E}\left[X_{n,p}^{H}\right]$, the upper tail event holds with ‘decent’ probability. This allows us to bound the lower tail probability from below by the probability of $C\subseteq G_{n,p}$ (which is $p^{e_{C}}$) times the ‘decent’ probability above (which is $p^{o(e_{C})}$). We refer to this as ‘planting a copy of $C$’. Of course one would like to consider the smallest such $C$, to increase the lower bound as much as possible.

In the previous works mentioned earlier, it was shown that for $\Delta$-regular graphs there are two natural candidates for $C$. These candidates are: a clique on $\Theta(np^{\Delta/2})$ vertices or a spanning complete bipartite graph with the smaller side of size $\Theta(np^{\Delta})$. The second construction is often called a Hub. When $p\ll n^{-1/\Delta}$, the small side of the Hub construction needs to be smaller than one and hence at that point the Hub construction is no longer valid, and we are left only with the clique construction as a lower bound for the upper tail probability. This is the reason for the two different regimes in Theorem 1.1.

Even though $C_{4}$ is a regular graph, the presence of a clique in $G_{n,p}$ does not boost the expected number of induced 4-cycles by a significant amount. Therefore, the first construction is no longer valid. The analog of this construction in our case is a balanced and complete bipartite graph with $\Theta(np)$ vertices. Surprisingly, although amongst all graphs with a given number of edges the complete and balanced bipartite graph maximizes the number of induced copies of $C_{4}$ (see [7, 19] and Lemma 6.2) planting it does not always give the strongest lower bound on the upper tail probability.

This is because, in a range of densities $p$, there is a large family $\mathcal{K}_{p}$ of subgraphs of $K_{n}$, where each $C\in\mathcal{K}_{p}$ satisfies $\mathbb{E}[X\mid C\subseteq G_{n,p}]\geq(1+\delta)\mathbb{E}[X]$ and has only slightly suboptimal size (amongst all $C$ with this property), that is so ‘large’ that

where the minimum ranges over all graphs $C$ with $\mathbb{E}[X\mid C\subseteq G_{n,p}]\geq(1+\delta)\mathbb{E}[X]$; moreover, conditioned on the event that $C\subseteq G_{n,p}$ for some $C\in\mathcal{K}_{p}$, the upper tail event still holds with ‘decent’ probability. Note that this is very different from the case of non-induced regular graphs, as here we condition on the appearance of some graph from $\mathcal{K}_{p}$ rather than a single graph (which corresponds to tilting the measure of $G_{n,p}$ to $G_{n,\bar{q}}$ for some $\bar{q}\in\{p,1\}^{\binom{n}{2}}$). In fact, we will show (in Section 7) that the lower bound obtained with the use of $\mathcal{K}_{p}$ is stronger than any bound corresponding to the more general tilting $G_{n,p}$ to $G_{n,\bar{q}}$ for some $\bar{q}\in[0,1]^{\binom{n}{2}}$.

Let us elaborate on the structure of the graphs in $\mathcal{K}_{p}$. The family $\mathcal{K}_{p}$ depends on $p$ in the following way: provided $n^{-1+c_{k-1}}\leq p\leq n^{-1+c_{k}}$ for some integer $k\geq 2$, the set $\mathcal{K}_{p}$ comprises all complete bipartite graphs with sides $k$ and $\ell=2\sqrt{\frac{\delta\mathbb{E}[X]}{k(k-1)}}$. Note that, for any fixed $k$ and large $n$, the graph $K_{k,\ell}$ has more edges than the complete and balanced bipartite graph with the same number of induced copies of $C_{4}$. However, the key point here is that we are no longer planting a single copy of this graph. Since $\ell$ is large, there are many embeddings of $K_{k,\ell}$ in $K_{n}$ and the probability that $G_{n,p}$ contains some such copy is affected by the combinatorial factor of the number of possible embeddings. It turns out that the lower bound obtained by considering these families is actually tight in the range where $\frac{\log^{9}(n)}{n}\ll p\ll n^{-2/3-o(1)}$. Further, between $\frac{\log^{9}(n)}{n}$ and $n^{-2/3-o(1)}$ the family $\mathcal{K}_{p}$ changes infinitely many times depending on $p$, which explains the infinite number of phase transitions. This will be explained in more details in Section 7.

We start with some notations and definitions which can also be found in [21]. We work within the probability space $(\{0,1\}^{N},\operatorname{Ber}({p})^{N})$. Suppose $I\subseteq[N]$ and $x\in\{0,1\}^{N}$. We say that

is a subcube centered at $(I,x)$ with codimension $|I|$ denoted by $\operatorname{codim}(F)=|I|$. Note that every subcube is centered at some pair $(I,x)$. Moreover, if a subcube $F$ is centered at $(I,x)$ and it is also centered at $(J,y)$ then $I=J$. Hence, the codimension is well defined. For every subcube $F$ centered at $(I,x)$ we define the one-supcube and the zero-supcube of $F$ to be $F^{(1)}=F(I_{1},x)$ and $F^{(0)}=F(I_{0},x)$ where $I_{i}=\{n\in I:x_{n}=i\}$ for $i=0,1$. Moreover, for every subcube $F$ we say that the one-codimension of it is the codimension of $F^{(1)}$ and the zero-codimension of it is the codimension of $F^{(0)}$ denoted by $\operatorname{codim}_{i}(F)$ for $i=1$ and $i=0$ respectively. A simple observation is that any subcube $F$ always satisfies $F=F^{(0)}\cap F^{(1)}$ and $\operatorname{codim}(F)=\operatorname{codim}(F^{(0)})+\operatorname{codim}(F^{(1)})$. For every $X\colon\{0,1\}^{N}\rightarrow\mathbb{R}_{\geq 0}$ we define the complexity of $X$ denoted by $\operatorname{comp}(X)$ to be the smallest integer $d$ for which it is possible to represent $X$ as a linear combination with nonnegative coefficients of indicator functions of subcubes with codimension at most $d$. Note that the complexity is well defined as for every such function $X$ we can write

Moreover, this shows that for any $X$ we have $\operatorname{comp}(X)\leq N$. Assume now that $Y$ is a random variable taking values in $\{0,1\}^{N}$ and that $X=X(Y)$. Given a subcube $F\subseteq\{0,1\}^{N}$, we write $\mathbb{E}_{F}[X]=\mathbb{E}[X\mid Y\in F]$ for the expectation of $X$ conditioned on $Y\in F$. We further define $\Phi_{X}\colon\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}\cup\{\infty\}$ by

Our main tool is [21, Theorem 9.1], which was stated but not proved. We prove a slightly different version of the theorem, but the essence remains the same.

To prove the theorem we state and prove the following lemmas.

Now we use the previous lemmas to prove the theorem.

When $p\ll 1$ and $\operatorname{comp}(X)=O(1)$, the majority of the contribution to both $\mathbb{E}_{F}[X]$ and $\mathbb{P}(Y\in F)$ comes from the one-supcube $F^{(1)}\supseteq F$. We prove a straightforward corollary of Theorem 2.1 which will be more convenient to work with. We start by proving the following lemma.

Using this lemma we now state and prove a straightforward corollary of Theorem 2.1.