Experimental mathematics colloquium

Jan Hladky: Loebl-Komlos-Sos conjecture

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.