报告题目：乘积图的导出子图有关定理的推广

报告人：赖虹建教授  西弗吉尼亚大学

报告时间：2021年7月7日上午 9:00-11:00

腾讯会议 ID：759202326

赖虹建教授个人简介：美国西弗吉尼亚大学数学系终身教授，博士生导师，国际知名的图论专家，主要研究领域包括图论中的欧拉子图、哈密尔顿性问题、整数流以及图论中的染色和连通度问题，出版学术著作两部，发表学术论文250余篇。完成了两部专著：由克鲁亚学术出版社（Kluwer Academic Publishing）出版的“图与组合学中的矩阵论”和由高等教育出版社出版的“拟阵论”。1996年获学院最优科研奖，2006年获学院最优教师奖和全校最优教师奖，成为西弗吉尼亚大学历史上第一个获此荣誉的华裔教授。曾主持过1996年由美国国家自然科学基金会资助的纪念凯特林（Catlin）教授的欧拉图问题专题会议，2008年由美国国家自然科学基金会资助的第46届美国中西部图论会议，以及2018年的第59届美国中西部图论会议。曾任Discrete Mathematics杂志客座编辑，现担任Applied Mathematics和Graphs and Combinatorics等多个杂志的编辑。

报告摘要：在计算机算法复杂性上的“Sensitivity Conjecture”认为对任何一个布尔函数f，计算这个函数的复杂性不会超过对应的决策树深度的一个多项式。C. Gotsman 和 N. Linial在[The equivalence of two problems on the cube, J. Combin. Theory, Ser. A, 61(1) (1992), 142—146]一文中证明了Sensitivity Conjecture等价于在n-维超立方体中，任何一个有2^{n-1}+1个顶点的导出子图的最大度至少是n的开方根。Hao Huang在[Induced graphs of the hypercube and a proof of the Sensitivity Conjecture, Ann. of Math., 190 (2019), 949--955]很巧妙地应用分块矩阵和特征根的技巧，最终证明了这个猜想。我们介绍Huang's theorem，以及关于推广这个定理的一些想法。