The deletion method for upper tail estimates

DOI10.1007/S00493-004-0038-3zbMath1074.60006OpenAlexW2096249319MaRDI QIDQ2567402

Svante Janson, Andrzej Ruciński

Publication date: 4 October 2005

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-004-0038-3

zbMATH Keywords

dependency graphrandom graphsums of random variables

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items (28)

Upper tails for subgraph counts in random graphs ⋮ The infamous upper tail ⋮ Nonlinear large deviations ⋮ The missing log in large deviations for triangle counts ⋮ Upper tails for triangles ⋮ On replica symmetry of large deviations in random graphs ⋮ Combinatorial theorems in sparse random sets ⋮ 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 ⋮ Large deviations in random latin squares ⋮ Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs ⋮ On the Method of Typical Bounded Differences ⋮ Concentration inequalities using the entropy method ⋮ When does the K₄‐free process stop? ⋮ On the variational problem for upper tails in sparse random graphs ⋮ Moment inequalities for functions of independent random variables ⋮ The lower tail: Poisson approximation revisited ⋮ On the missing log in upper tail estimates ⋮ A counterexample to the DeMarco‐Kahn upper tail conjecture ⋮ Upper tail bounds for stars ⋮ Approximation algorithms for channel allocation problems in broadcast networks ⋮ Regular graphs with many triangles are structured ⋮ The C_ℓ‐free process ⋮ On the average-case complexity of parameterized clique ⋮ Upper bounds on probability thresholds for asymmetric Ramsey properties ⋮ Tight upper tail bounds for cliques

This page was built for publication: The deletion method for upper tail estimates