Upper tail large deviations of regular subgraph counts in sparse random regular graphs
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 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, and also identify the typical structure of $\mathbb{G}_n^d$ conditioned on this upper tail event. For $Δ\geq 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.31590
curl -X POST /api/v1/records/arxiv/2610.31590/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.31590/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'