DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

A Probabilistic Counting Lemma for Complete Graphs

Stefanie Gerke, Martin Marciniszyn, Angelika Steger


We prove the existence of many complete graphs in almost all sufficiently dense partitions obtained by an application of Szemerédi's Regularity Lemma. More precisely, we consider the number of complete graphs Kℓ on ℓ vertices in ℓ-partite graphs where each partition class consists of n vertices and there is an ε-regular graph on m edges between any two partition classes. We show that for all β> 0, at most a βm-fraction of graphs in this family contain less than the expected number of copies of Kℓ provided ε is sufficiently small and m ≥Cn2-1/(ℓ-1) for a constant C > 0 and n sufficiently large. This result is a counting version of a restricted version of a conjecture by Kohayakawa, 1;uczak and Rödl [MR1479298] and has several implications for random graphs.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional