Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, August 11, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Martin Marciniszyn
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 Kl on l vertices in l-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 Kl provided ε is sufficiently small and m >= Cn2-1/(l-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, Luczak, and Rödl (1997) and has several implications for random graphs.
This is joint work with Stefanie Gerke and Angelika Steger.
Automatic MiSe System Software Version 1.4803M | admin login