Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 19, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Rajko Nenadov
Szemeredi's regularity lemma, together with the corresponding embedding and counting lemmas, is an important tool in modern graph theory. However, because of the underlying definition of regularity it is only helpful when one is dealing with dense graphs, that is, graphs of density cn^2 for some constant c. In 1997, Kohayakawa and Rödl introduced a modification of regularity that makes it applicable to the certain class of graphs with density o(n^2), and Kohayakawa, Luczak and Rödl conjectured a corresponding embedding lemma. The embedding conjecture has been proven only recently, and using some stronger assumptions the counting version was derived. We show that the counting lemma for some special cases, namely K4, K5 and K6, can be proven using the same setup as the embedding conjecture without any additional assumptions.
Thesis supervised by Angelika Steger.
Automatic MiSe System Software Version 1.4803M | admin login