2022/02/14 by Shirshendu Ganguly, Ganguly, Shirshendu, Ella Hiesmayr +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.2202.06916
32 pages, 2 figures
arxiv created 2022/02/14 · arxiv updated 2022/02/15
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 d3/6 as n→ ∞. We address the upper tail problem for N, namely, we investigate how fast k must grow, so that the probability of \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 k1/3 log k< ((3)/(√(2)))2/3 log n (sub-critical regime) as well as pin down the tail behavior when k1/3 log k> ((3)/(√(2)))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, culminating in (Harel, Moussat, Samotij,'19) 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.