The Loebl-Komlos-Sos conjecture

Datum

08.01.2015

Zeit

13:15 - 14:15

Sprecher

Jan Hladky

Zugehörigkeit

Czech Academy of Sciences, Prague

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Prof. Dr. M. Bodirsky / Prof. Dr. A. Thom

Beschreibung

Many problems in extremal graph theory fit in the following framework: Does a certain density condition imposed on a host graph guarantee the existence of a given subgraph? Perhaps the most famous example in this direction is Mantel's Theorem from 1907: If a graph on n vertices contains at more than n^2/4 edges, then it must contain a triangle. I will give further examples, explain the basic concepts of extremal graphs and stability, and show the role of the celebrated Szemeredi Regularity Lemma in proving similar results. I will then report on joint progress with Janos Komlos, Diana Piguet, Miklos Simonovits, Maya Stein, Endre Szemeredi on the Loebl-Komlos-Sos conjecture, an extremal problem about containment of trees, which has been open for two decades.

Links

• Seminar Algebra, Geometrie und Kombinatorik

Letztmalig verändert: 27.11.2014, 15:42:42