Upper tails for triangles (Q2904594)

This paper makes progress with the notorious problem of the upper tail for the number of copies of a fixed graph in a random graph, in the case of triangles, and the techniques in fact extend to cliques (see below). More precisely, let \(G(m,p)\) be the random graph with labelled vertices \([m]=\{1,2,\ldots m\}\) and each possible edge present with probability \(p=p(m)\). Let \(\xi\) denote the number of triangles in the graph, so that \(\mathbb{E}(\xi)={m\choose 3}p^{3}\). The first result in the paper is that, given \(\eta>0\), provided \(p(m)>\ln(m)/m\), NEWLINE\[NEWLINE\mathbb{P}(\xi>(1+\eta)\mathbb{E}(\xi))<p^{\Omega_{\eta}(m^{2}p^{2})}=\exp(-\Omega_{\eta}(m^{2}p^{2}\log(1/p))).NEWLINE\]NEWLINE The bound is tight up to the value of the implied constant, as the probability that there is a complete graph on \(2mp\) vertices is of the same order.NEWLINENEWLINEThe second result of the paper is a lower bound on \(\mathbb{P}(\xi>(1+\eta)\mathbb{E}(\xi))\) when \(1/m<p\leq \ln(m)/m\), namely that, unless \(2p^{3}\geq 1\), we have NEWLINE\[NEWLINE\mathbb{P}(\xi>2\mathbb{E}(\xi))>\exp(-O(m^{3}p^{3})).NEWLINE\]NEWLINE In fact this is proved for a somewhat larger range of \(p\) (up to, say, \(m^{-5/6}\), though for values of \(p\) above \(\ln(m)/m\) the result is not news.) Note that for \(p<1/m\) the question is uninteresting.NEWLINENEWLINEIt is then natural to ask what is the correct rate of decay. Basically, it turns out that the lower of the two upper bounds above is the correct answer, and that this is tight. This is Theorem 1.3 of the paper, that for any \(\eta>0\) we have NEWLINE\[NEWLINE\mathbb{P}(\xi>(1+\eta){m\choose 3}p^{3})<\exp(-\Omega_{\eta}(\min\{m^{2}p^{2}\log(1/p),m^{3}p^{3}\}) ).NEWLINE\]NEWLINENEWLINENEWLINEThe proof of the main result Theorem 1.3. proceeds by noting that it is sufficient to prove the analogous result for the number of triangles in a random tripartite graph and then proving that result by proving various pseudo-random properties of the set of triangles using standard bounds on binomials.NEWLINENEWLINESince writing this paper, the authors have generalised their techniques to other cliques (and in fact slightly more: their upper bound works for any graph on \(k\) vertices with minimum degree \(k-2\)) [\textit{B. de Marco} and \textit{J. Kahn}, ``Tight upper tail bounds for cliques,'' Random Struct. Algorithms, to appear, \url{http://dx.doi.org/10.1002/rsa.20440}].