Universality in prelimiting tail behavior for regular subgraph counts in the Poisson regime

Mriganka Basu Roy Chowdhury¹

¹University of California, Berkeley

The electronic journal of combinatorics, Tome 32 (2025) no. 3

Résumé

Let $N$ be the number of copies of a small subgraph $H$ in an Erdős-Rényi 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á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 $\mathbb{P}(N \geq k_n)$ 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_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 for the tail probabilities 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.

Détail

DOI : 10.37236/13443

Classification : 05C80, 60F10, 05C30
Mots-clés : Erdős-Rényi graph, sparse random graphs, nonlinear large deviations, upper tails