Stefanie Gerke ; Martin Marciniszyn ; Angelika Steger

A Probabilistic Counting Lemma for Complete Graphs
dmtcs:3464 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3464
A Probabilistic Counting Lemma for Complete GraphsArticle
Authors: Stefanie Gerke ^{1}; Martin Marciniszyn ^{1}; Angelika Steger ^{1}
NULL##NULL##NULL
Stefanie Gerke;Martin Marciniszyn;Angelika Steger
1 Institute of Theoretical Computer Science [Zurich]
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^{21/(\ell1)}$ 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.
Funder: Natural Sciences and Engineering Research Council of Canada
Fundamental Algorithms based on Random Sampling, Convex Relaxation, and Spectral Analysis; Funder: National Science Foundation; Code: 0721503
Bibliographic References
4 Documents citing this article
Graham Brightwell;Konstantinos Panagiotou;Angelika Steger, 2012, Extremal subgraphs of random graphs, Random Structures and Algorithms, 41, 2, pp. 147178, 10.1002/rsa.20413.
S. Gerke;H. J. Prömel;T. Schickinger;A. Steger;A. Taraz, 2007, K 4free subgraphs of random graphs revisited, Repository for Publications and Research Data (ETH Zurich), 27, 3, pp. 329365, 10.1007/s0049300720105, http://hdl.handle.net/20.500.11850/7404.