2023/04/03 by Mriganka Basu Roy Chowdhury, Chowdhury, Mriganka Basu Roy
Mathematics · #Stochastic processes and statistical mechanics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2304.01162
Let N be the number of copies of a small subgraph H in an Erdős-Rényi graph G ∼ G(n, pn) where pn → 0 is chosen so that 𝔼 N = c, a constant. Results of Bollobás show that for regular graphs H, the count N weakly converges to a Poisson random variable. For large but finite n, and for the specific case of the triangle, investigations of the upper tail ℙ(N ≥ kn) by Ganguly, Hiesmayr and Nam (2022) revealed that there is a phase transition in the tail behavior and the associated mechanism. Smaller values of kn correspond to disjoint occurrences of H, leading to Poisson tails, with a different behavior emerging when kn is large, guided by the appearance of an almost clique. We show that a similar phase transition also occurs when H is any regular graph, at the point where kn1 -2/qlog kn = log n (q is the number of vertices in H). This establishes universality of this transition, previously known only for the case of the triangle.