|
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.
|
|
|
|