***********************************
                * 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)