***********************************
* Princeton Discrete Math Seminar *
***********************************
Date: Thursday 16th March, 3:00 in Fine Hall 224.
Speaker: Alex Scott (Oxford)
Title: Stability results for graphs with a critical edge
The classical stability theorem of Erdos and Simonovits states
that, for a fixed nonbipartite graph H with chromatic number k+1, every
n-vertex graph that is H-free and has within o(n^2) of the maximal
possible number of edges can be made into the k-partite TurĀ“an graph by
adding and deleting o(n^2) edges. We prove sharper quantitative results
for graphs H with a critical edge, both for distance to the Turan graph,
and for the closely related question of how close an H-free graph is to
being k-partite. In many cases, these results are optimal to within a
constant factor.
Joint work with Alex Roberts (Oxford).
Next two weeks: no seminar. Week after: Maryanthe Malliaris
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)