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

Source 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 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 $\mathbb{G}_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 $\mathbb{G}_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 \ll n^{v_H}p^{e_H} \ll (\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.