Upper tail bounds for Stars
arXiv:1901.10637 · doi:10.37236/8493
Abstract
For r \ge 2, let X be the number of r-armed stars K_{1,r} in the binomial random graph G_{n,p}. We study the upper tail \Pr(X \ge (1+ε)\E X), and establish exponential bounds which are best possible up to constant factors in the exponent (for the special case of stars K_{1,r} this solves a problem of Janson and Rucinski, and confirms a conjecture by DeMarco and Kahn). In contrast to the widely accepted standard for the upper tail problem, we do not restrict our attention to constant ε, but also allow for ε\ge n^{-α} deviations.
arXiv comment14 pages
References in corpus (12)
- On replica symmetry of large deviations in random graphs
- Upper tails for triangles
- On the method of typical bounded differences
- Upper tails and independence polynomials in random graphs
- On the variational problem for upper tails in sparse random graphs
- Upper Tails for Cliques
- Upper tails for arithmetic progressions in random subsets
- 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
- Large deviations of subgraph counts for sparse Erdős--Rényi graphs