Upper Tail Bounds for Stars

0523427 - ÚI 2021 RIV US eng J - Journal Article
Šileikis, Matas - Warnke, L.
Upper Tail Bounds for Stars.
Electronic Journal of Combinatorics. Roč. 27, č. 1 (2020), č. článku P1.67. ISSN 1077-8926. E-ISSN 1077-8926
R&D Projects: GA ČR GJ16-07822Y; GA ČR(CZ) GJ20-27757Y
Institutional support: RVO:67985807
Keywords : Subgraph counts * random graphs * concentration inequalities * upper tail * large deviations
OECD category: Pure mathematics
Impact factor: 0.695, year: 2020
Method of publishing: Open access

For r ≥ 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 P(X ≥ (1+ε)EX), 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 ε, but also allow for ε ≥ n^(-a) deviations.
Permanent Link: http://hdl.handle.net/11104/0307782