Upper tails for triangles

DOI10.1002/RSA.20382zbMath1246.05142arXiv1005.4471OpenAlexW1965433673MaRDI QIDQ2904594

Bobby DeMarco, Jeffry Kahn

Publication date: 14 August 2012

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

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

zbMATH Keywords

random graphslarge deviationssubgraph countsupper tails

Mathematics Subject Classification ID

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

Related Items (30)

Nonlinear large deviations ⋮ The missing log in large deviations for triangle counts ⋮ 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 ⋮ 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 ⋮ 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 ⋮ 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 ⋮ A counterexample to the DeMarco‐Kahn upper tail conjecture ⋮ Limit laws for the number of triangles in the generalized random graphs with random node weights ⋮ An introduction to large deviations for random graphs ⋮ Upper tail bounds for stars ⋮ Regular graphs with many triangles are structured ⋮ Concentration inequalities on the multislice and for sampling without replacement ⋮ Rate of Convergence to the Poisson Law of the Numbers of Cycles in the Generalized Random Graphs ⋮ Tight upper tail bounds for cliques

Cites Work

• Unnamed Item
• Applications of Stein's method for concentration inequalities
• Upper tails for subgraph counts in random graphs
• The deletion method for upper tail estimates
• On the Choice Number of Random Hypergraphs
• Divide and conquer martingales and the number of triangles in a random graph
• The infamous upper tail

This page was built for publication: Upper tails for triangles