Tight upper tail bounds for cliques

DOI10.1002/rsa.20440zbMath1255.05172arXiv1111.6687MaRDI 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 graphs; large deviations; subgraph counts; upper tails

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Upper Tail Bounds for Cycles, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, A counterexample to the DeMarco‐Kahn upper tail conjecture, On the variational problem for upper tails in sparse random graphs, Upper tail for homomorphism counts in constrained sparse random graphs, 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, Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, Upper tails for arithmetic progressions in random subsets, Upper tails via high moments and entropic stability, Nonlinear large deviations: beyond the hypercube, 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, On the missing log in upper tail estimates, Upper tail bounds for stars, Upper tails and independence polynomials in random graphs, Nonlinear large deviations, The lower tail: Poisson approximation revisited, An introduction to large deviations for random graphs, On replica symmetry of large deviations in random graphs

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