  Let $N$ be the number of copies of a small subgraph $H$ in an
Erd\H{o}s-R\'enyi graph $G \sim \mathcal{G}(n, p_n)$ where $p_n \to 0$ is
chosen so that $\mathbb{E} N = c$, a constant. Results of Bollob\'as 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 $\mathbb{P}(N \geq k_n)$ by Ganguly, Hiesmayr
and Nam (2022) revealed that there is a phase transition in the tail behavior
and the associated mechanism. Smaller values of $k_n$ correspond to disjoint
occurrences of $H$, leading to Poisson tails, with a different behavior
emerging when $k_n$ 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 $k_n^{1 -2/q}\log k_n = \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.

Probability;Combinatorics