Upper tails for triangles

Abstract

With $\xi$ the number of triangles in the usual (Erdős-Rényi) random graph $G(m,p)$, $p>1/m$ and $\eta >0$, we show (for some $C_{\eta }>0$) $$\Pr(ξ> (1+η)\E ξ) < \exp[-C_η\min{m^2p^2\log(1/p),m^3p^3}].$$ This is tight up to the value of $C_{\eta }$.

10 pages

References in corpus (1)

• Upper tails for triangles

Cited by in corpus (22)

• On replica symmetry of large deviations in random graphs
• Upper tails for triangles
• Upper tails and independence polynomials in random graphs
• On the variational problem for upper tails in sparse random graphs
• Upper Tails for Cliques
• Upper tails for arithmetic progressions in random subsets
• On the lower tail variational problem for random graphs
• 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
• Upper tail bounds for Stars
• On rate of convergence to the Poisson law of the number of cycles in the generalized random graphs
• De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions
• Modified log-Sobolev inequalities and two-level concentration
• Concentration inequalities on the multislice and for sampling without replacement
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Regular graphs with linearly many triangles
• Upper Tails of Subgraph Counts in Sparse Regular Graphs
• A large deviation principle for block models
• The missing log in large deviations for triangle counts
• Concentration inequalities in spaces of random configurations with positive Ricci curvatures
• On the upper tail problem for random hypergraphs