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, 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

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

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