Upper tail large deviations of regular subgraph counts in sparse random regular graphs
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 𝔾nd, a random d-regular graph on n vertices, in the regime npΔ/2 ≫ (log n)1/(vH−2) and p ≪ 1, where p:=d/n and vH is the number of vertices, and also identify the typical structure of 𝔾nd conditioned on this upper tail event. For Δ≥ 3, the speed and the rate function are same with those in the Erdős-Rényi setting. In contrast, for Δ=2 (i.e.~in case of cycles), due to the degree constraint in 𝔾nd, although speed remains the same the rate function turns out to be different. Moreover, conditioned on the upper tail event of cycle counts in 𝔾nd, we show that the random graph contains a disjoint collection of clique and biclique like structures with probability approaching to one, a stark contrast compared to the Erdős-Rényi setting. In the complementary regime, i.e.~for 1 ≪ nvHpeH ≪ (log n)α*H/(α*H−1), where eH is the number of edges in H, α*H is the fractional independence number of H, and H is a strictly balanced graph (and thus including the regular case), 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 of the unlabeled copies of H conditioned on the upper tail event are edge disjoint.
Related
- Normal approximation for subgraph counts in random intersection graphs: the case of cliques
- Fluctuations of subgraph counts in exponential random graphs
- Moderate Deviations for Random-Indexed Cluster Counts in Hierarchical Pitman-Yor Models
- The lower tail of triangle counts in sparse random graphs
- Local large deviations for triangles in sparse random graphs
BibTeX
@misc{basak2026upper,
title = {{Upper tail large deviations of regular subgraph counts in sparse random regular graphs}},
author = {Anirban Basak and Shaibal Karmakar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31590},
eprint = {2610.31590},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31590},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Upper tail large deviations of regular subgraph counts in sparse random regular graphs
AU - Anirban Basak
AU - Shaibal Karmakar
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31590
UR - https://arxiv.org/abs/2610.31590
AB - 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 𝔾_n^d, a random d-regular graph on n vertices, in the regime np^Δ/2 ≫ (log n)^1/(v_H−2) and p ≪ 1, where p:=d/n and v_H is the number of vertices, and also identify the typical structure of 𝔾_n^d conditioned on this upper tail event. For Δ≥ 3, the speed and the rate function are same with those in the Erdős-Rényi setting. In contrast, for Δ=2 (i.e.~in case of cycles), due to the degree constraint in 𝔾_n^d, although speed remains the same the rate function turns out to be different. Moreover, conditioned on the upper tail event of cycle counts in 𝔾_n^d, we show that the random graph contains a disjoint collection of clique and biclique like structures with probability approaching to one, a stark contrast compared to the Erdős-Rényi setting. In the complementary regime, i.e.~for 1 ≪ n^v_Hp^e_H ≪ (log n)^α^*_H/(α^*_H−1), where e_H is the number of edges in H, α^*_H is the fractional independence number of H, and H is a strictly balanced graph (and thus including the regular case), 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 of the unlabeled copies of H conditioned on the upper tail event are edge disjoint.
ER -