Upper tail bounds for stars (Q2309238)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper tail bounds for stars |
scientific article |
Statements
Upper tail bounds for stars (English)
0 references
30 March 2020
0 references
Summary: 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+\varepsilon)\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 \textit{S. Janson} and \textit{A. Ruciński} [Ark. Mat. 49, No. 1, 79--96 (2011; Zbl 1223.05201)], and confirms a conjecture by \textit{B. DeMarco} and \textit{J. Kahn} [Random Struct. Algorithms 40, No. 4, 452--459 (2012; Zbl 1246.05142)]). In contrast to the widely accepted standard for the upper tail problem, we do not restrict our attention to constant \(\varepsilon \), but also allow for \(\varepsilon \ge n^{-\alpha}\) deviations.
0 references
binomial random graph
0 references
\(r\)-armed stars
0 references
0 references
0 references
0 references