The missing log in large deviations for triangle counts

DOI10.1002/RSA.20381zbMath1246.05140arXiv1003.3498OpenAlexW2034538428MaRDI QIDQ2904593

Sourav Chatterjee

Publication date: 14 August 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1003.3498

zbMATH Keywords

large deviationsconcentration inequalitiesErdős-Rényi random graphtail bound

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (34)

Nonlinear large deviations ⋮ A tail bound for read-kfamilies of functions ⋮ On replica symmetry of large deviations in random graphs ⋮ Modified log-Sobolev inequalities and two-level concentration ⋮ Moderate deviations via cumulants ⋮ Upper tails via high moments and entropic stability ⋮ Upper tails and independence polynomials in random graphs ⋮ Localization in random geometric graphs with too many edges ⋮ Upper tails for arithmetic progressions in random subsets ⋮ On the upper tail problem for random hypergraphs ⋮ Upper tail for homomorphism counts in constrained sparse random graphs ⋮ Moderate deviations in cycle count ⋮ Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph ⋮ Lower tails via relative entropy ⋮ The upper tail problem for induced 4‐cycles in sparse random graphs ⋮ Large deviations in random latin squares ⋮ Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime ⋮ Large deviations of subgraph counts for sparse Erdős-Rényi graphs ⋮ On the Lower Tail Variational Problem for Random Graphs ⋮ Unnamed Item ⋮ Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs ⋮ The large deviation principle for the Erdős-Rényi random graph ⋮ Upper Tail Bounds for Cycles ⋮ Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order ⋮ On the variational problem for upper tails in sparse random graphs ⋮ The lower tail: Poisson approximation revisited ⋮ On the missing log in upper tail estimates ⋮ A counterexample to the DeMarco‐Kahn upper tail conjecture ⋮ An introduction to large deviations for random graphs ⋮ Upper tail bounds for stars ⋮ Regular graphs with many triangles are structured ⋮ Lower large deviations for geometric functionals ⋮ Concentration inequalities on the multislice and for sampling without replacement ⋮ Tight upper tail bounds for cliques

Cites Work

• Applications of Stein's method for concentration inequalities
• The large deviation principle for the Erdős-Rényi random graph
• When are small subgraphs of a random graph normally distributed?
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• Concentration inequalities using the entropy method
• Upper tails for subgraph counts in random graphs
• Concentration of measure and isoperimetric inequalities in product spaces
• The deletion method for upper tail estimates
• On the Choice Number of Random Hypergraphs
• Upper tails for triangles
• Threshold functions for small subgraphs
• Poisson approximation for large deviations
• Divide and conquer martingales and the number of triangles in a random graph
• Concentration of non‐Lipschitz functions and applications
• The infamous upper tail
• Probability Inequalities for Sums of Bounded Random Variables
• Concentration of multivariate polynomials and its applications

This page was built for publication: The missing log in large deviations for triangle counts