Tight upper tail bounds for cliques

DOI10.1002/rsa.20440zbMath1255.05172arXiv1111.6687OpenAlexW1980423003MaRDI QIDQ3145838

Bobby DeMarco, Jeffry Kahn

Publication date: 14 December 2012

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

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

zbMATH Keywords

random graphslarge deviationssubgraph countsupper tails

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Nonlinear large deviations ⋮ On replica symmetry of large deviations in random graphs ⋮ Upper tails via high moments and entropic stability ⋮ Upper tails and independence polynomials in random graphs ⋮ Upper tails for arithmetic progressions in random subsets ⋮ Upper tail for homomorphism counts in constrained sparse random graphs ⋮ Nonlinear large deviations: beyond the hypercube ⋮ The upper tail problem for induced 4‐cycles in sparse random graphs ⋮ 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 ⋮ 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 ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ 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

Cites Work

• Unnamed Item
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On the number of copies of one hypergraph in another
• Upper tails for subgraph counts in random graphs
• The deletion method for upper tail estimates
• On the Choice Number of Random Hypergraphs
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Poisson approximation for large deviations
• Divide and conquer martingales and the number of triangles in a random graph
• On the concentration of multivariate polynomials with small expectation
• The infamous upper tail
• Concentration of multivariate polynomials and its applications