*********************************** * Princeton Discrete Math Seminar * *********************************** Speaker: Bernard Lidicky (Iowa State U) Thursday 15th March, 3:00 in Fine Hall 224. Title: On large bipartite subgraphs in dense H-free graphs A long-standing conjecture of Erdő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 edges. Moreover, this amount is needed only in the case G that 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üredi on stable version of Turán's theorem. This is joint work with P. Hu, T. Martins-Lopez, S. Norin and J. Volec. --------------------------------------------- Next week: spring break, no seminar; week after, Tinaz Ekim Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)