A large deviation result on the number of small subgraphs of a random graph (Q2722658)

This paper applies a new martingale inequality of \textit{J. H. Kim} and \textit{V. H. Vu} [Concentration of multivariate polynomials and applications, Combinatorica 20, No. 3, 417-434 (2000; Zbl 0969.60013)] to the following random variable: Given a fixed graph \(H\) and given a positive integer \(n\) and \(p \in [0, 1]\), let \(Y_H\) be the number of copies of \(H\) in a random graph \(G_{n,p}\). There are a number of papers on this r.v\(.\) for \(H\) balanced. This paper concentrates on the upper tail of \(Y_H\): the primary theorem says that for appropriate \(\varepsilon > 0\), if \(H\) is balanced and has \(k\) vertices, and if \({\mathbf E}[Y_H]\) grows sufficiently rapidly as \(n \to \infty\), then \({\mathbf {Pr}}[Y_H \geq (1 + \varepsilon){\mathbf E}(Y_H)] \leq \exp(-\text{ const}\cdot \varepsilon^2{\mathbf E}(Y_H))^{1/(k-1)}\). A corollary of this result---involving the fractional independence number of \(H\)---is somewhat sharp. The proof of this result proceeds via a generalization of the primary theorem to a r.v\(.\) counting the number of extensions of a subgraph of \(H\).