Upper Tails for Cliques

Abstract

With ${\xi }_k={\xi }_k^{n,p}$ the number of copies of $K_k$ in the usual (Erdős-Rényi) random graph $G(n,p)$, $p\ge n^{-2/(k-1)}$ and $\eta >0$, we show when $k>1$ $$\Pr(ξ_k> (1+η)\E ξ_k) < \exp [-\gO_{η,k} \min\{n^2p^{k-1}\log(1/p), n^kp^{\binom{k}{2}}\}].$$ This is tight up to the value of the constant in the exponent.

25 pages

Cited by in corpus (15)

• On replica symmetry of large deviations in random graphs
• Upper tails and independence polynomials in random graphs
• On the variational problem for upper tails in sparse random graphs
• Upper tails for arithmetic progressions in random subsets
• The lower tail: Poisson approximation revisited
• Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdös-Renyi graphs
• Upper tails for arithmetic progressions in a random set
• A counterexample to the DeMarco-Kahn Upper Tail Conjecture
• On the missing log in upper tail estimates
• Upper tail bounds for Stars
• Nonlinear Large Deviations: Beyond the Hypercube
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Local resilience of an almost spanning $k$-cycle in random graphs
• A large deviation principle for block models
• Concentration inequalities in spaces of random configurations with positive Ricci curvatures