A probabilistic counting lemma for complete graphs
We prove the existence of many complete graphs in almost all sufficiently dense partitions obtained by an application of Szemeredi's regularity lemma. More precisely, we consider the number of complete graphs K-l on (l) vertices in (l)-partite graphs where each partition class consists of n vertices and there is an epsilon-regular graph on m edges between any two partition classes. We show that for all beta > 0, at most a beta(m)-fraction of all such graphs contain a little less than the expected number of copies of K-l provided epsilon is sufficiently small, m >> n(2-1/(l-1)), and n is sufficiently large. This result is a counting version of a restricted version of a conjecture (Kohayakawa, Luczak, and Rodl, Combinatorica 17 (1997), 173-213), and it is well known that this result implies several results for random graphs. 0 2007 Wiley Periodicals, Inc.
counting lemma szemeridi regularity sparse graph turans problem in random graphs