Geodesic
A Probabilistic Counting Lemma for Complete Graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a73,
     author = {Gerke, Stefanie and Marciniszyn, Martin and Steger, Angelika},
     title = {A {Probabilistic} {Counting} {Lemma} for {Complete} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3464},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3464/}
}
TY  - JOUR
AU  - Gerke, Stefanie
AU  - Marciniszyn, Martin
AU  - Steger, Angelika
TI  - A Probabilistic Counting Lemma for Complete Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3464/
DO  - 10.46298/dmtcs.3464
LA  - en
ID  - DMTCS_2005_special_250_a73
ER  - 
%0 Journal Article
%A Gerke, Stefanie
%A Marciniszyn, Martin
%A Steger, Angelika
%T A Probabilistic Counting Lemma for Complete Graphs
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3464/
%R 10.46298/dmtcs.3464
%G en
%F DMTCS_2005_special_250_a73
Gerke, Stefanie; Marciniszyn, Martin; Steger, Angelika. A Probabilistic Counting Lemma for Complete Graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3464. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3464/

Cité par Sources :