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 GraphsConference paper
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ℓ 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, Łuczak and Rödl and has several implications for random graphs.
Fundamental Algorithms based on Random Sampling, Convex Relaxation, and Spectral Analysis; Funder: National Science Foundation; Code: 0721503
Funder: Natural Sciences and Engineering Research Council of Canada
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. 147-178, 10.1002/rsa.20413.
S. Gerke;H. J. Prömel;T. Schickinger;A. Steger;A. Taraz, 2007, K 4-free subgraphs of random graphs revisited, Repository for Publications and Research Data (ETH Zurich), 27, 3, pp. 329-365, 10.1007/s00493-007-2010-5, http://hdl.handle.net/20.500.11850/7404.