Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Mathias Schacht - HU Berlin

Regularity lemmas for graphs and hypergraphs

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

Han Hiep - HU Berlin

Weak pseudo-random hypergraphs

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.

Letzte Aktualisierung: 26.01.2009