On the missing log in upper tail estimates
arXiv:1612.08561 · doi:10.1016/j.jctb.2019.05.003
Abstract
In the late 1990s, Kim and Vu pioneered an inductive method for showing concentration of certain random variables X. Shortly afterwards, Janson and Ruci{ń}ski developed an alternative inductive approach, which often gives comparable results for the upper tail Pr(X \ge (1+\eps) E[X]). In some cases, both methods yield upper tail estimates which are best possible up to a logarithmic factor in the exponent, but closing this narrow gap has remained a technical challenge. In this paper we present a BK-inequality based combinatorial sparsification idea that can recover this missing logarithmic term in the upper tail. As an illustration, we consider random subsets of the integers {1,...,n}, and prove sharp upper tail estimates for various objects of interest in additive combinatorics. Examples include the number of arithmetic progressions, Schur triples, additive quadruples, and (r,s)-sums.
arXiv comment31 pages; minor edits; to appear in Journal of Combinatorial Theory, Series B (JCTB)
References in corpus (10)
- Extremal results for random discrete structures
- A quantitative improvement for Roth's theorem on arithmetic progressions
- On the method of typical bounded differences
- Upper Tails for Cliques
- Upper tails for arithmetic progressions in random subsets
- When does the K_4-free process stop?
- The lower tail: Poisson approximation revisited
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- The Janson inequalities for general up-sets
- A counterexample to the DeMarco-Kahn Upper Tail Conjecture