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 ${\mathbb P}(X \ge (1+\epsilon){\mathbb 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 Ruciński, 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 $\epsilon$, but also allow for $\epsilon \ge n^{-\alpha}$ deviations.
@article{10_37236_8493,
author = {Matas \v{S}ileikis and Lutz Warnke},
title = {Upper tail bounds for stars},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/8493},
zbl = {1435.05183},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8493/}
}
TY - JOUR
AU - Matas Šileikis
AU - Lutz Warnke
TI - Upper tail bounds for stars
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8493/
DO - 10.37236/8493
ID - 10_37236_8493
ER -
