# A Probabilistic Counting Lemma for Complete Graphs

Abstract : 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_{\ell}$ on $\ell$ vertices in $\ell$-partite graphs where each partition class consists of $n$ vertices and there is an $\varepsilon$-regular graph on $m$ edges between any two partition classes. We show that for all $\beta >$0, at most a $\beta^m$-fraction of graphs in this family contain less than the expected number of copies of $K_{\ell}$ provided $\varepsilon$ is sufficiently small and $m \geq Cn^{2-1/(\ell-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, Łuczak and Rödl and has several implications for random graphs.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [15 references]

https://hal.inria.fr/hal-01184453
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:59:42 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:14:47 AM

### File

dmAE0161.pdf
Publisher files allowed on an open archive

### Citation

Stefanie Gerke, Martin Marciniszyn, Angelika Steger. A Probabilistic Counting Lemma for Complete Graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.309-316, ⟨10.46298/dmtcs.3464⟩. ⟨hal-01184453⟩

Record views