Upper Tail Bounds for Stars

0523427 - ÚI 2021 RIV US eng J - Článek v odborném periodiku
Š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
Grant CEP: GA ČR GJ16-07822Y; GA ČR(CZ) GJ20-27757Y
Institucionální podpora: RVO:67985807
Klíčová slova: Subgraph counts * random graphs * concentration inequalities * upper tail * large deviations
Obor OECD: Pure mathematics
Impakt faktor: 0.695, rok: 2020
Způsob publikování: 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.
Trvalý link: http://hdl.handle.net/11104/0307782