Professur Theoretische Informatik und Informationssicherheit
Herr Lucas de Oliveira Contiero
Universidade Federal do Rio Grande do Sul
Porto Alegre, Brasilien
"The Regularity Lemma for graphs and some applications"
11:30 - 13.00 Uhr, Straße der Nationen 62, 1/B006
Alle interessierten Personen sind herzlich eingeladen!
The Regularity Lemma, introduced by Szemer´edi, informally claims that the vertices of any large graph can be partitioned into a constant number of classes with nearly the same size so that for almost every pair of classes, the edges between these classes are approximately randomly distributed.
This very important result has been stated in different ways for graphs and hypergraphs and, together with another very important result called Embedding Lemma, it has been used to prove stability results in Extremal Graph Theory and in (algorithmic and non-algorithmic) problems involving colorings of graphs.
In this talk, among others, a formal treatment of the Regularity Lemma will be presented with some applications.