University of Cambridge > > Combinatorics Seminar > A Stability Theorem for Maximal K_{r+1}-free graphs

A Stability Theorem for Maximal K_{r+1}-free graphs

Add to your list(s) Download to your calendar using vCal

  • UserRichard Snyder (University of Memphis)
  • ClockThursday 09 June 2016, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason.

We prove a stability result for maximal Kr+1-free graphs. More precisely, let G be a maximal Kr+1-free graph whose number of edges is at most m away from the maximum possible in any Kr+1-free graph. We determine a function f(n) such that if m=o(f(n)), then G necessarily contains an induced complete r-partite subgraph which nearly spans the entire vertex set. We also provide constructions showing that this function f is best possible. This work resolves questions of Tyomkyn and Uzzell.

Joint with Kamil Popielarz and Julian Sahasrabudhe.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity