Back to Search
Start Over
Upper tail bounds for Stars
- Source :
- The Electronic Journal of Combinatorics 27 (2020), Article P1.67
- Publication Year :
- 2019
-
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+\epsilon)\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 \epsilon, but also allow for \epsilon \ge n^{-\alpha} deviations.<br />Comment: 14 pages
- Subjects :
- Mathematics - Probability
Mathematics - Combinatorics
05C80, 60C05, 60F10
Subjects
Details
- Database :
- arXiv
- Journal :
- The Electronic Journal of Combinatorics 27 (2020), Article P1.67
- Publication Type :
- Report
- Accession number :
- edsarx.1901.10637
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.37236/8493