题  目：Maximizing the Number of  Proper Colorings in Graphs

报告人：马  杰， 教授（中国科大学院）

时  间：2014年6月7日（星期六）    上午 9:50－10:50

地  点：管理科研楼1611会议室

摘  要：This talk report a joint work with Humberto Naves on an old problem of Linial and Wilf to find graphs with n vertices and m edges which maximize the number of proper vertex- -colorings. Loh, Pikhurko and Sudakov asymptotically reduced the problem to an optimization problem. This talk proves the following result: for any instance, each solution of the optimization problem corresponds to either a complete multipartite graph or a graph obtained from a complete multipartite graph by removing certain edges. Apply this result to general instances, including a conjecture of Lazebnik from 1989 which asserts that for any  , the Turan graph   has the maximum number of  -colorings among all graphs with the same number of vertices and edges. This conjecture is disproved by providing infinity many counterexamples in the interval  . On the positive side, when   the Turan graph indeed achieves the maximum number of  -colorings.

报告人简介：科大2003级校友，2011年获佐治亚理工学院博士学位，师从著名的国际图论专家郁星星教授，2011年-2014先后在美国加州大学洛杉矶分校和和卡内基梅隆大学从事博士后研究。2013年加盟中国科大。研究方向为组合与图论，在极值组合，结构图论，概率组合等前沿领域得到了一系列重大创新成果，特别在超图划分，图兰类问题，四色定理推广，随机图以及flag algebras等重要研究领域中做出令国际同行公认的研究成果，得到Bela Bollobas和Benny Sudakov等国际顶尖组合图论专家和知名学者的极高赞誉。
 
主办单位: 
365英国上市官网
中科院吴文俊数学重点实验室

欢迎感兴趣的师生参加!