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

Let N be the number of triangles in an Erdős–Rényi 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 → ∞ . 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 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 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 (6 k) 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. [ABSTRACT FROM AUTHOR]