Monday, February 2, 2009
Institut für Informatik
Rudower Chaussee 25
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Szemeredi's regularity lemma is a powerful tool in extramal graph theory, which had have many applications. In this talk we present several variants of Szemeredi's original lemma (due to several researchers including Frieze and Kannan, Alon et al., and Lovasz and Szegedy) and discuss their relation to each other. We also consider several different looking regularity lemmas for hypergraphs of which some, but not all, turn out to be equivalent.
Colloquium - 16:00
Random graphs have proven to be a fruitful concept in Combinatorics and Theoretical Computer Science. This evokes the question which properties make a graph random-like and leads to the notion of pseudo-random graphs. The systematic study of this subject was initiated by Thomasen in the 80's and in their classical paper Chung, Graham, and Wilson gave a long list of equivalent properties characterising pseudo-random graphs.
In this talk we will focus on weak pseudo-random hypergraphs, a straightforward generalisation of pseudo-random graphs to $k$-uniform hypergraphs. In particular, we derive a result similar to the one by Chung, Graham, and Wilson.
This is a joint work with David Conlon, Yury Person, and Mathias Schacht.