Upper Tail Behavior of the Number of Triangles in Random Graphs with Constant Average Degree

Abstract

Let N be the number of triangles in an Erdos-Renyi graph G(n, p) on n vertices with edge density p = d/n, where d > 0 is a fixed constant. It is well known that N weakly converges to the Poisson distribution with mean d(3)/6 as n ->infinity. We address the upper tail problem for N, namely, we investigate how fast k must grow, so that P(N >= k) is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when k(1/3) log k < (3/root 2 - o(1))(2/3) log n (sub-critical regime) as well as pin down the tail behavior when k(1/3) log k > (3/root 2 + o(1))(2/3) log n (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost k vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately (6k)(1/3). This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades and culminating in Harel et al. (Duke Math J 171(10):2089-2192, 2022), which analyzed the problem only in the regime p >> 1/n. The proofs rely on several novel graph theoretical results which could have other applications.