Abstract: Furedi proved that every $K_{r+1}$-free graph G with n vertices and m edges can be made r-partite by removing at most (r-1)n^2/2r - m edges. We investigate strengthenings of his result. For r < 5, we show that every $K_{r+1}$-free graph G with n vertices and m edges can be made r-partite by removing at most 0.8((r-1)n^2/2r - m) edges, and conjecture that the same is true for every r. We show that this conjecture implies a solution of a problem of Sudakov on making $K_{r+1}$-free graphs bipartite for large r. Finally, we show that every $K_6$-free graph G on n vertices can be made bipartite by removing at most $4n^2/25$ edges, solving the case r=5 of Sudakov's problem.
Our main tool is Razborov's flag algebras. Joint work with Bernard Lidicky, Taisa Martins, Sergey Norin and Jan Volec.
Speaker: 胡平于2014年在美国伊利诺伊大学香槟分校(University of Illinois at Urbana-Champaign)获得数学博士学位，之后在英国华威大学(University of Warwick)任研究员(Research Fellow)，2017年入职中山大学任副教授。其研究方向是极值组合，主要包括Ramsey理论，Turan理论及染色问题。
Zoom Information:
https://us05web.zoom.us/j/86538395196?pwd=eVZMdnAvaWM2b0tyYTAvS3ZvdkxZUT09
Conference Number: 865 3839 5196
Password: JYtb6U
