The lower tail: Poisson approximation revisited
summary
Proves sharp lower-tail asymptotics for subgraph counts in G(n,p): when each indicator probability max(pi) -> 0 and dependency measure Δ -> 0 and ε^2·E[X_H] -> ∞, the probability X_H ≤ (1−ε)E[X_H] decays like exp(−Φ_H(ε)·E[X_H]) (Poisson-type exponent). Uses Janson-style upper bounds, Stein–Chen/Poisson approximation, correlation inequalities, Laplace-transform integration and a reduction by conditioning on a minimizing subgraph (e.g. K4→“Santa Claus” gadget) to extend beyond the strict Poisson range. Previously only upper bounds existed; the new lower bounds match them.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:24Motivation
- 7:54Qualitative behavior
- 9:55Cross on case
- 10:53Inequality
- 14:33Channel type inequality
- 15:54Concentration inequality
- 17:34Maximum over expectation
- 18:12Natural assumptions
- 21:30Remarks
- 26:13The House of Santa Claus
- 41:24Summary
- 42:06Soft argument
related talks
24mRobust Parameter Estimation For Random Graphs
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
01h 31mGraphons and Graph Limits 2
40mOn Learning Graph Binomial Distributions and Powers of Poisson Binomial Distributions
01h 03mHigh Dimensional Geometry and Concentration II
44mThreshold, Influence, Noise, and Discrete Harmonic Analysis
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IV