Speaker: Hou Jianfeng, professor, doctoral supervisor

Date: Wednesday, June 15, 2022

Time: 9:00-10:00

Location: Tencent Meeting

Sponsor: School of Mathematics, Shandong University

Abstract:

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. (Joint work with Wu Shufei)

For more information, please visit:

https://view.sdu.edu.cn/info/1020/166651.htm