Local large deviations for triangles in sparse random graphs

Source abstract

We revisit a classic topic in probabilistic combinatorics, the lower-tail large-deviation problem for triangles in the random graph $G(n,p)$. Here we aim for first-order asymptotics for the quantity $\mathbb{P}[X=k]$ with $X$ the number of triangles in $G(n,p)$ and $0 \le k \le (1-ε) \mathbb{E}X$, in the sparse regime in which the logarithmic asymptotics are Poissonian. When $k=0$ (the case of triangle-freeness) and $p = p(n)$ is sufficiently small, first-order asymptotics are known via Janson's inequality and results of Stark and Wormald; when $k$ is sufficiently close to $\mathbb{E}X$, first-order asymptotics are known via local central limit theorems. Our main result gives first-order asymptotics for all $k$ in the above range when $p = o(n^{-2/3})$, improving upon the result of Frieze that required $p = o(n^{-4/5})$. We also characterize, up to vanishing total variation distance, the distribution of the $k$ triangles in the corresponding conditional distribution and give an efficient algorithm to approximately sample from this conditional distribution. Notably, when $k = Θ(μ)$ there is a transition at $p = Θ(n^{-4/5})$ from an asymptotically uniform triangle distribution to a distribution asymptotically singular to uniform.