A concentration result with application to subgraph count
Let H = (V,E) be a k -uniform hypergraph with a vertex set V and an edge set E. Let Vp be constructed by taking every vertex in V independently with probability p. Let X be the number of edges in E that are contained in Vp. We give a condition that guarantees the concentration of X within a small interval around its mean. The applicability of this result is demonstrated by deriving new sub-Gaussian tail bounds for the number of copies of small complete and complete bipartite graphs in the binomial random graph.  2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012
concentration result subgraph count sub-gaussian tail bounds random graphs