Universality in Prelimiting Tail Behavior for Regular Subgraph Counts in the Poisson Regime

Let N be the number of copies of a small subgraph H in an Erdős-Rényi graph G G (n, pₙ) where pₙ 0 is chosen so that E N = c, a constant. Results of Bollobás (1981) 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 P (N kₙ) by Ganguly, Hiesmayr and Nam Combinatorica 44, 2024 revealed that there is a phase transition in the tail behavior and the associated mechanism. Smaller values of kₙ correspond to disjoint occurrences of H, leading to Poisson tails, with a different behavior emerging when kₙ is large, guided by the appearance of an almost clique. We show that a similar phase transition also occurs for the tail probabilities when H is any regular graph, at the point where kₙ^1 -2/q kₙ = n (q is the number of vertices in H). This establishes universality of this transition, previously known only for the case of the triangle.