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 withedges, one expectsedges spans in one vertex class.and Scott [Random Struct. Alg. 21 (2002) 414–430] asked for conditions that guarantee a bisection in which both classes span at mostedges simultaneously. Let be integers with, and let G be a graph with minimum degreeand m edges. In this talk, we prove that if G contains neither triangle noras a subgraph, then G admits a bisection in which both classes span at mostedges. (Join work with Shufei Wu)
Introduction to the Lecturer:
Hou Jianfeng, Professor and Doctoral Supervisor, graduated from the School of Mathematics, Shandong University with a doctor of science degree in July 2009. Hou Jianfeng was not only nominated for the National Excellent Doctoral Dissertation Award in 2011, but also was the winner of the outstanding youth program of Fujian Provincial Natural Science Foundation in 2011. In 2020, Hou Jianfeng was selected as a top-notch young talent of Fujian "Baby Eagle Plan", and in 2021, Hou Jianfeng was selected as a Young Chang Jiang Scholars Program. Besides, Hou Jianfeng presided over 4 projects of the National Natural Science Foundation and participated in one key project. At present, Hou Jianfeng is a member of the professional committee of combinatorial mathematics and graph theory of Chinese Mathematical Society, the professional committee of graph theory and application of China Society for Industrial and Applied Mathematics, the executive director of Fujian Mathematical Society and the Young AE of frontier of Frontiers of Computer Science. Hou Jianfeng is mainly engaged in the research of graph and hypergraph partition theory, and has published more than 60 academic papers.
Jin Yan, Professor at the School of Mathematics
9:00-10:00, June 15 (Wednesday)
Contact: Jin Yan Tel.: 139 6405 5656
Sponsored by: School of Mathematics, Shandong University