Local large deviations for triangles in sparse random graphs

Jade Lintott; Will Perkins; Corrine Yap

En palabras de los autores

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 $P [X = k]$ with $X$ the number of triangles in $G (n, p)$ and $0 \leq k \leq (1 - ϵ) 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 $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.

Resultado principalLimitación que admiten los autores

Local large deviations for triangles in sparse random graphs

En palabras de los autores

Más de Probabilidad ese día

SpaceDiffusion: Over-the-Orbit Diffusion for Space Generate-and-Forward Communications

A Probabilistic Modeling Framework for Transient Debris Outcomes in Low Lunar Orbits

Total Variation Distance between Product Distributions: an Analytic Proxy

The joint exit time and exit location law of a planar Ornstein-Uhlenbeck process on annular sectors and principal axis rectangles

Sharp High-Entropy Bounds for Sums of Independent Discrete Random Variables