报告题目：Large multipartite subgraphs in H-free graphs

报 告 人：胡平教授

报告时间：2022年5月16日14:30-15:30

报告地点：腾讯会议 （ID：111 795 151）

邀请单位：bat365在线登录入口，

离散数学及其应用省部共建教育部重点实验室

报告内容简介：

 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.

报告人简介：

胡平于2014年在美国伊利诺伊大学香槟分校获得数学博士学位，之后在英国华威大学任研究员，2017年入职中山大学任副教授。其研究方向是极值组合，主要包括Ramsey理论，Turan理论及染色问题。