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
    0 references
    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
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references