一、题目

On bisections of graphs without complete bipartite graphs

二、主讲人

侯建锋

三、摘要

A bisection of a graph is a bipartition of its vertex set in which the two classes differ in size by at most one. For a random bisection of a graph with m edges, one expects m/4 edges spans in one vertex class. Bolloba ́s and Scott [Random Struct. Alg. 21 (2002) 414–430] asked for conditions that guarantee a bisection in which both classes span at most (1/4 + o(1))m edges simultaneously. Let δ,l be integers with l≥δ≥ 2, and let G be a graph with minimum degree δ and m edges. In this talk, we prove that if G contains neither triangle nor K_(δ,l) as a subgraph, then G admits a bisection in which both classes span at most (1/4 + o(1))m edges. (Join work with Shufei Wu)

四、主讲人简介

侯建锋，教授，博士生导师。2009年7月毕业于山东大学数学学院，获理学博士学位。2011年度全国优秀博士学位论文提名奖，2011年度福建省自然科学基金杰出青年项目获得者，2020年入选福建省“雏鹰计划”青年拔尖人才，2021年入选青年长江学者计划，主持国家自然科学基金4项，参与重点项目一项。目前为中国数学会组合数学与图论专业委员会委员，中国工业与应用数学学会图论组合及应用专业委员会委员，福建省数学会常务理事，Frontiers of Computer Science青年AE。主要从事图与超图划分理论方面的研究，发表学术论文60余篇。

五、邀请人

颜谨 数学学院教授

六、时间

6月15日（周三）9:00-10:00

七、地点

腾讯会议

八、主办

山东大学数学学院