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

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