Upper Tails of Subgraph Counts in Sparse Regular Graphs

Abstract

What is the probability that a sparse $n$-vertex random $d$-regular graph $G_n^d$, $n^{1-c}=o(n)$ contains many more copies of a fixed graph $K$ than expected? We determine the behavior of this upper tail to within a logarithmic gap in the exponent. For most graphs $K$ (for instance, for any $K$ of average degree at least $4$) we determine the upper tail up to a $1+o(1)$ factor in the exponent. However, we also provide an example of a graph, given by adding an edge to $K_{2,4}$, where the upper tail probability behaves differently from previously studied behavior in both the sparse random regular and sparse Erd\H{o}s-R'{e}nyi models in this sparsity regime.