The deletion method for upper tail estimates

DOI10.1007/S00493-004-0038-3MaRDI QIDQ2567402zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Upper tails for subgraph counts in random graphs
• The infamous upper tail
• Tight upper tail bounds for cliques
• A large deviation result on the number of small subgraphs of a random graph
• Upper tails for triangles
• A concentration result with application to subgraph count
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• When are small subgraphs of a random graph normally distributed?
• Many cliques in \(H\)-free subgraphs of random graphs

Cited in

(35)

• Random deletion does not affect asymptotic normality or quadratic negligibility
• Concentration inequalities using the entropy method
• Upper tails for arithmetic progressions in random subsets
• Moment inequalities for functions of independent random variables
• Upper tails for subgraph counts in random graphs
• Regular graphs with many triangles are structured
• Upper tails via high moments and entropic stability
• On the missing log in upper tail estimates
• Upper tail bounds for stars
• On the average-case complexity of parameterized clique
• Upper tails and independence polynomials in random graphs
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• Nonlinear large deviations
• The lower tail: Poisson approximation revisited
• Upper bounds on probability thresholds for asymmetric Ramsey properties
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Combinatorial estimates by the switching method
• Tight upper tail bounds for cliques
• On replica symmetry of large deviations in random graphs
• Combinatorial theorems in sparse random sets
• General deletion lemmas via the Harris inequality
• The infamous upper tail
• A counterexample to the DeMarco-Kahn upper tail conjecture
• On the method of typical bounded differences
• When does the \(K_{4}\)-free process stop?
• Approximation algorithms for channel allocation problems in broadcast networks
• The C_ℓ‐free process
• On the variational problem for upper tails in sparse random graphs
• Upper tail for homomorphism counts in constrained sparse random graphs
• Large deviations in random latin squares
• A large deviation principle for block models
• On the upper tail of star counts in random graphs
• Large deviation principles for graphon sampling
• Large deviations for subgraphs in inhomogeneous random graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2567402)