#
Monday Lecture and Colloquium

**Monday, June 27, 2011 **

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

###
Benny Sudakov - UCLA

### Extremal Graph Theory and its applications

*Abstract:*

In typical extremal problem one wants to determine maximum cardinality of
discrete structure with certain prescribed properties. Probably the
earliest such result was obtain 100 years ago by Mantel who computed the
maximum number of edges in a triangle free graph on n vertices. This was
generalized by Turan for all complete graphs and became a starting point
of Extremal Graph Theory. In this talk we survey several classical
problems and results in this area and present some interesting
applications of Extremal Graph Theory to other areas of mathematics. We
also describe a recent surprising generalization of Turan's theorem which
was motivated by question in Computational Complexity.

**Colloquium - 16:00**

###
Roman Glebov - FU Berlin

### On Extremal Hypergraphs for Hamiltonian Cycles

*Abstract:*

We study sufficient conditions for Hamiltonian cycles in hypergraphs, and
obtain both Tur\'an- and Dirac-type results.

While the Tur\'an-type result gives an exact threshold for the appearance
of a Hamiltonian cycle in a hypergraph depending only on the extremal
number of a certain path, the Dirac-type result yields just a sufficient
condition relying solely on the minimum vertex degree.

Joint work with Yury Person and Wilma Weps.

Letzte Aktualisierung:
07.06.2011