Graphs, limits and property testing

Speaker: Mathias Schacht

Affiliation: Humboldt U. at Berlin, Germany

Abstract: Szemeredi's regularity lemma is a powerful tool in extramal graph theory, which had have many applications. In this talk we present different stronger and weaker variants of Szemeredi's original lemma. In particular, we discuss the recent approach of Lovasz and Szegedy and the connections to property testing.



Hypergraph regularity lemmas: Equivalences and differences

Speaker: Mathias Schacht

Affiliation: Humboldt U. at Berlin, Germany

Abstract: Several "different looking" extensions of Szemeredi's regularity lemma, from graphs to k-uniform hypergraphs, were obtained in recent years. In this talk we survey those approaches. We discuss recent results (joint with Nagle and Rödl), which say that some, but not all, of those regularity lemmas for hypergraphs are equivalent.