Overview
A mathematical study deposited on the arXiv investigates the upper tail large deviations behavior for regular subgraph counts in sparse random regular graphs $\mathbb{G}_n^d$. Focusing on a $\Delta$-regular connected graph $H$ with $v_H$ vertices and edge density parameter $p := d/n$, the work establishes the large deviation speeds and rate functions governing the number of copies of $H$ across two distinct regimes, while characterizing the typical structural configurations of the random graph conditioned on these upper tail events.
Research Context
In probabilistic combinatorics, large deviations for subgraph counts quantify the exponentially small probabilities that a random graph exhibits significantly more copies of a target subgraph than expected. While these properties have been extensively analyzed in the binomial Erd\H{o}s-R\'enyi random graph model $\mathbb{G}(n,p)$, the hard degree constraints of random regular graphs $\mathbb{G}_n^d$ introduce structural dependencies that alter subgraph distributions and the resulting variational problems.
Approach
The analysis investigates two separate regimes of sparsity:
- A dense-to-sparse regime defined by $np^{\Delta/2} \gg (\log n)^{1/(v_H-2)}$ and $p \ll 1$, where $H$ is a $\Delta$-regular connected graph.
- A complementary sparse regime characterized by $1 \ll n^{v_H}p^{e_H} \ll (\log n)^{\alpha^*_H/(\alpha^*_H-1)}$, where $e_H$ denotes the number of edges in $H$, $\alpha^*_H$ is the fractional independence number of $H$, and $H$ is strictly balanced.
Within these domains, the authors derive the precise large deviation speeds and rate functions and analyze the typical geometry of $\mathbb{G}_n^d$ conditioned on the upper tail occurrence.
Findings
The study reveals structural bifurcations depending on the regularity degree $\Delta$ and the edge sparsity regime:
- High-degree regular subgraphs ($\Delta \geq 3$): In the regime $np^{\Delta/2} \gg (\log n)^{1/(v_H-2)}$ with $p \ll 1$, both the upper tail large deviations speed and the rate function for the number of copies of $H$ in $\mathbb{G}_n^d$ match those found in the Erd\H{o}s-R\'enyi random graph model.
- Cycle counts ($\Delta = 2$): Under the same regime, when $H$ is a collection of cycles (degree $\Delta = 2$), the degree constraint of $\mathbb{G}_n^d$ drives a departure from Erd\H{o}s-R\'enyi behavior. While the speed parameter remains identical, the rate function differs. Conditioned on the upper tail event, the typical structure of $\mathbb{G}_n^d$ exhibits a disjoint collection of clique-like and biclique-like structures with probability tending to one.
- Complementary regime for strictly balanced graphs: For strictly balanced graphs $H$ satisfying $1 \ll n^{v_H}p^{e_H} \ll (\log n)^{\alpha^*_H/(\alpha^*_H-1)}$, the speed and rate function match the Erd\H{o}s-R\'enyi setting. Furthermore, conditional on the upper tail event in this regime, almost all unlabeled copies of $H$ are edge disjoint.