Local large deviations for triangles in sparse random graphs

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-\epsilon )\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=\Theta (\mu )$ there is a transition at $p=\Theta (n^{-4/5})$ from an asymptotically uniform triangle distribution to a distribution asymptotically singular to uniform.

44 pages, 4 figures