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
partners


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

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

Han Hiep - HU Berlin


Weak pseudo-random hypergraphs

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.




Letzte Aktualisierung: 26.01.2009