The lower tail: Poisson approximation revisited

DOI10.1002/rsa.20590zbMath1332.05128arXiv1406.1248OpenAlexW3100287411MaRDI QIDQ2795741

Svante Janson, Lutz Warnke

Publication date: 22 March 2016

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

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

zbMATH Keywords

large deviationsconcentration inequalitysubgraph countsJanson's inequalitylower tail

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorial probability (60C05)

Related Items

Upper tails via high moments and entropic stability, Upper tails for arithmetic progressions in random subsets, Upper tail for homomorphism counts in constrained sparse random graphs, Deviation probabilities for arithmetic progressions and other regular discrete structures, Counting extensions revisited, Moderate deviations in cycle count, Deviation probabilities for arithmetic progressions and irregular discrete structures, Large deviations of subgraph counts for sparse Erdős-Rényi graphs, Local limit theorems for subgraph counts, On the Method of Typical Bounded Differences, On the Lower Tail Variational Problem for Random Graphs, Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs, Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝), On the missing log in upper tail estimates, Bivariate fluctuations for the number of arithmetic progressions in random sets, A counterexample to the DeMarco‐Kahn upper tail conjecture, Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\), Upper tail bounds for stars, A general method for lower bounds on fluctuations of random variables, Lower large deviations for geometric functionals

Cites Work

• Unnamed Item
• On the upper tail of counts of strictly balanced subgraphs
• The large deviation principle for the Erdős-Rényi random graph
• When are small subgraphs of a random graph normally distributed?
• Correlation inequalities on some partially ordered sets
• Upper tails for arithmetic progressions in random subsets
• Upper tails for subgraph counts in random graphs
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• The deletion method for upper tail estimates
• Counting extensions
• On the Choice Number of Random Hypergraphs
• The missing log in large deviations for triangle counts
• Tight upper tail bounds for cliques
• Threshold functions for small subgraphs
• Poisson convergence and random graphs
• Poisson approximation for large deviations
• A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
• Colorings generated by monotone properties
• New versions of Suen's correlation inequality
• The Janson inequalities for general up‐sets
• Independent sets in hypergraphs
• Concentration of multivariate polynomials and its applications