×

A large deviation result on the number of small subgraphs of a random graph. (English) Zbl 0982.05092

This paper applies a new martingale inequality of J. H. Kim and 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\).
Reviewer: G.L.McColm (Tampa)

MSC:

05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability

Citations:

Zbl 0969.60013
Full Text: DOI