Paperlane

no. 15 · Monday 16 November 2026

Upper tail large deviations of regular subgraph counts in sparse random regular graphs

Anirban Basak and Shaibal Karmakar

math.PR · v2 · 64 pp

Abstract

For a $Δ$-regular connected graph $H$ we obtain the upper tail large deviations speed and rate function for the number of copies of $H$ in $\mathbb{G}_n^d$, a random $d$-regular graph on $n$ vertices, in the localized regime $np^{Δ/2}\gg(\log n)^{1/(v_H-2)}$ and $p\ll 1$, where $p:=d/n$ and $v_H$ is the number of vertices in $H$, and identify the typical structure of $\mathbb{G}_n^d$ conditioned on this rare event. The degree constraint in $\mathbb{G}_n^d$ changes the Erdős-Rényi picture in two ways. First, the hub construction that competes with a clique in the regime $p \gg n^{-1/Δ}$ is not feasible here. Consequently, for $Δ\geq 3$ throughout the entire localized regime, both the rate function and the conditional structure are governed by a planted almost-clique, of size roughly $δ^{1/v_H}np^{Δ/2}$. Second, as no clique in $\mathbb{G}_n^d$ can be of size greater than $(d+1)$, for $Δ=2$ (i.e.~in case of cycles), the rate function and the conditional structure are governed by $\lfloorδ\rfloor$ many planted almost-cliques of size roughly $d$ and another planted almost-clique of size roughly $\{δ\}^{1/v_H}d$. For cycles of even length, in lieu of pairs of almost-cliques each of size roughly $d$, the conditional structure may possess copies of almost-bicliques with each side roughly of size $d$. In the complementary regime $1\ll n^{v_H}p^{e_H}\ll(\log n)^{α^*_H/(α^*_H-1)}$, where $e_H$ is the number of edges and $α^*_H$ is the fractional independence number of $H$, and $H$ is a strictly balanced graph (and thus including regular $H$), we show that the upper tail large deviations speed and rate function for the number of copies of $H$ match with those in the Erdős-Rényi setting. In this regime, we further show that almost all unlabeled copies of $H$ conditioned on the upper tail event are edge disjoint.

comments
64 pages, 2 figures; Conditional-ER result added (Theorems A.1 and A.2)
fields
Probability, Combinatorics
pdf ↗ page arXiv:2610.31590 ↗