The deletion method for upper tail estimates (Q2567402): Difference between revisions

Let \(\{Y_\alpha,\alpha\in \mathcal A\}\) be a family of nonnegative random variables, where \(\mathcal A\) is a finite set with a symmetric relation \(\sim\). Assume that every \(Y_\alpha\) is independent of \(\{Y_\beta:\beta\sim\alpha\}\). Set \(X=\sum_\alpha Y_\alpha\) and \(\mu=EX\). An upper tail estimate \[ P(X\geq \mu+t)\leq (1+t/2\mu)^{-r}+P \left(\max_\alpha\sum_{\beta\sim\alpha}Y_\beta>t/2r\right) \] with arbitrary \(r>0\) is obtained. This basic estimate is proved by a new method called deletion method. The rest of the paper is devoted to derivations of several estimates from this basic one in the case \(\mathcal A\) consists of subsets of some index set and \(\alpha\sim\beta\) means that \(\alpha \cap\beta\) has some minimal cardinality. A comparison of the obtained results with that of \textit{J. H. Kim} and \textit{V. H. Vu} [Combinatorica 20, 417--434 (2000; Zbl 0969.60013)] is proved. Applications to the number \(X_G\) of copies of a graph \(G\) in the random graph \(G(n,p)\) are given. In particular, some known upper bounds for the cases \(G=K_4\) and \(G=C_4\) are essentially improved.