Springe zum Hauptinhalt
Fakultät für Informatik


265. Informatik-Kolloquium


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"


Mittwoch, 01.02.2017
11:30 - 13.00 Uhr, Straße der Nationen 62, 1/B006

Alle interessierten Personen sind herzlich eingeladen!

The Regularity Lemma for graphs and some applications
Lucas  de Oliveira Contiero
UFRGS, Porto Alegre, Brazil

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.