MATH Seminar

Title: On large multipartite subgraphs of H-free graphs
Seminar: Combinatorics
Speaker: Jan Volec of McGill Univeristy
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2018-03-26 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: A long-standing conjecture of Erd\H{o}s states that any n-vertex triangle-free graph can be made bipartite by deleting at most $n^2/25$ edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most $4n^2/25+O(n)$ edges. In the case of $H=K_6$, we actually prove the exact bound $4n^2/25$ and show that this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of $F\ddot{u}redi$ on stable version of $Tur\acute{a}n's$ theorem. This is a joint work with P. Hu, B. $Lidick\acute{y}$, T. Martins-Lopez and S. Norin.