Premium
A concentration result with application to subgraph count
Author(s) -
Wolfovitz Guy
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20371
Subject(s) - combinatorics , hypergraph , bipartite graph , mathematics , vertex (graph theory) , random graph , complete bipartite graph , enhanced data rates for gsm evolution , discrete mathematics , graph , interval (graph theory) , computer science , telecommunications
Let H = ( V , E ) be a k ‐uniform hypergraph with a vertex set V and an edge set E . Let V p 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 V p . 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