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.