Stability methods and extremal graph theory

Miklos Simonovits
Renyi Institute of Mathematics

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
2. We can prove that all the almost extremal structures are near to the
property P, in some sense.
3. If we knew that if a structure is near to the property 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.

Back to Workshop III: Topics in Graphs and Hypergraphs