2019/12/24 by Anirban Basak, Basak, Anirban, Riddhipratim Basu +1 · 1 citation
Mathematics · #05C80 #60C05 #60F10 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1912.11410
openalex publication_date 2019/12/24 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
For a Δ-regular connected graph \sf H the problem of determining the upper tail large deviation for the number of copies of \sf H in \mathbbG(n,p), an Erdős-Rényi graph on n vertices with edge probability p, has generated significant interests. For p≪ 1 and npΔ/2 ≫ (log n)^1/(v\sf H-2), where v\sf H is the number of vertices in \sf H, the upper tail large deviation event is believed to occur due to the presence of localized structures. In this regime the large deviation event that the number of copies of \sf H in \mathbbG(n,p) exceeds its expectation by a constant factor is predicted to hold at a speed n2 pΔ log (1/p) and the rate function is conjectured to be given by the solution of a mean-field variational problem. After a series of developments in recent years, covering progressively broader ranges of p, the upper tail large deviations for cliques of fixed size was proved by Harel, Mousset, and Samotij \citehms in the entire localized regime. This paper establishes the conjecture for all connected regular graphs in the whole localized regime.