A Probabilistic Counting Lemma for Complete Graphs

Stefanie Gerke 1 Martin Marciniszyn 1 Angelika Steger 1
1 Institute of Theoretical Computer Science [Zurich]
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 : random graph regularity lemma combinatorial counting
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.309-316, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01184453
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:59:42
Dernière modification le : jeudi 11 mai 2017 - 01:02:53
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:14:47

Fichier

dmAE0161.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184453, version 1

Collections

INSMI | TDS-MACS

Citation

Stefanie Gerke, Martin Marciniszyn, Angelika Steger. A Probabilistic Counting Lemma for Complete Graphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.309-316, 2005, DMTCS Proceedings. 〈hal-01184453〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

127

Contact


archive-ouverte@inria.fr