Discrete Mathematics and Optimization Seminar
Feb. 10th, 2011

4:00 PM Burnside 920
Stability Method in Extremal Combinatorics
Oleg Pikhurko
Carnegie Mellon University
Abstract: A number of powerful asymptotic tools and methods such as (hyper)graph regularity and flag algebras have been developed for tackling problems of extremal combinatorics. Since these techniques deal with some approximation of the problem, they produce only approximate bounds.

The stability method introduced by Simonovits in the 1960s greatly helps with obtaining exact results from asymptotic calculations. The first step here is to establish the stability property which, roughly speaking, states that all almost extremal configurations have asymptotically the same structure. We discuss this method on the example of a few extremal problems centered around the Turan function ex(n,F), the maximum size of an F-free graph of order n.