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