Stability results for graphs with a critical edge

Thursday, March 16, 2017 -
3:00pm to 4:30pm
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). 
Alex Scott
Oxford University
Event Location: 
Fine Hall 224