Stability methods and extremal graph theory

Combinatorics Seminar
Friday, November 13, 2009 - 3:05pm for 2 hours
Skiles 255
Miklos Simonovits – Alfred Renyi Institute, Budapest, Hungary
Robin Thomas

Stability methods are often used in extremal graph theory, Ramsey theory and similar areas, where an extremal problem is to be solved and

  1. we have a conjecture about the structure of the conjectured extremal configurations and according to our conjecture, it has some given property \mathcal P;
  2. we can prove that all the almost extremal structures are near to the property \mathcal P, in some sense;
  3. if we knew that if a structure is near to the property \mathcal P and is extremal, then it is already the conjectured structure.

Of course, stability methods can also be used in other cases, but we restrict ourselves to the above two areas.

In my lecture I will give an introduction to the applications of the stability methods in extremal graph theory, describe cases in extremal graph theory, extremal hypergraph theory, in the Erdos-Frankl-Rold (= generalized Erdos-Kleitman-Rothschild theory) ...

In the second part of my lecture I shall describe the application of this method to the Erdos-Sos conjecture. This is part of our work with Ajtai, Komlos and Szemeredi.