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

  • 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^{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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: random graph,regularity lemma,combinatorial counting,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • 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

4 Documents citing this article

Consultation statistics

This page has been seen 201 times.
This article's PDF has been downloaded 514 times.