Monday, February 2, 2009
Humboldt-Universität Berlin
Institut für Informatik
Rudower Chaussee 25
Humboldt-Kabinett, 1st floor, between house III and IV
12489 Berlin
Lecture - 14:15
Abstract:
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
Abstract:
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.