2018年7月9日-13日，由北京大学前沿计算研究中心承办的“计算理论周”系列讲座在北京大学静园五院举行。“理论周”由中心邓小铁老师发起及组织，邀请计算机理论方面的多位知名专家学者，介绍计算机理论方向的前沿课题，并就相关问题和同学们开展深入讨论。

　　刘田老师的报告题目为“Tree Convex Bipartite Graphs”，其关注了两类不同的组合问题。

　　第一部分继续了第一天关于树凸二部图的内容，除了介绍（树）凸二部图的判定问题与组合刻画以外，还描述了一些经典NPC问题在限制在这类树上以后的复杂度二分类问题。例如Geodetic Set Problem对于弦二部图是NPC的（因此对于一般的二部图或一般的图都是NPC的），但人们尚不了解这个问题在树凸二部图上的限制是什么难度的。除此以外，就这类图本身的性质而言，也有不少开放的问题。曾经有人猜想，3-正则平面图有哈密顿回路；后来，Tutte给出了一个反例推翻了这个猜想；25年后，Tutte猜想3-正则二部图是哈密顿图，然而5年后这个猜想就被Horton推翻了。这两个猜想的结合，即问3-正则二部平面图是不是哈密顿图，仍然是开放的。这个问题在（树）凸二部图的限制也仍然留待解决。

　　第二部分介绍了一个知名的组合猜想。这个猜想的形式很简单，问对于一个包含至少2个集合的、对并运算封闭的有限集合的簇，是否存在一个元素使得它在至少一半的集合里出现过。这个“一半”是紧的，因为任何一个集合的子集簇，所有的元素恰好在一半的集合里出现过。这个问题看上去很单纯，但解决起来困难重重，因此有人评价：The 'union-closed sets conjecture' is well known indeed, except for (1) its origin and (2) its answer! 为了解决这个问题，人们尝试引入了不少技巧，例如将该猜想的元素计数的版本转换成集合平均大小的版本，或是加强原猜想的性质等等。同时，这个猜想和树凸二部图有一些联系，因为人们证明了，对于满足树凸性质的集族，这个猜想是成立的。

报告人简介：

　　刘田，北京大学信息学院计算机系副教授，主要研究方向为算法分析与计算复杂性理论。主持过两项国家自然科学基金项目以及多项其他研究课题，发表了多篇论文和译著。长期主讲“集合论与图论”、“理论计算机科学基础”等课程，2006年和2013年先后两次获得了北京大学教学优秀奖。