报告人： 侯建锋 教授 福州大学 报告时间: 2018年11月11日上午9:30-10:30 报告地点: 精正楼307教室 报告摘要: Bollobas and Scott [Problems and results on judicious partitions, Random Struct. Alg. 21 (2002) 414--430] asked for conditions that guarantee a bisection of a graph with m edges in which each class has at most (1/4+o(1))m edges. We demonstrate that cycles of length 4 play an important role for this question. Let G be a graph with m edges, minimum degree δ, and containing no cycle of length 4. We show that if (i) G is 2-connected, or (ii) δ≥ 3$, or (iii) δ≥ 2 and the girth of G is at least 5, then G admits a bisection in which each class has at most (1/4+o(1)m edges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollobas, Krivelevich and Sudakov shows that for infinitely many m there exists a graph with m edges and girth at least 5 for which any bisection has at least (1/4-o(1)m edges in one of the two classes. We also discuss the Max-bisections of graphs without short cycles.