Large and judicious bisections of graphs

Large and judicious bisections of graphs

Tue, 24/04/2012
14:30 		Choongbum Lee (UCLA) Combinatorial Theory Seminar Add to calendar L3
Large and judicious bisections of graphs
It is very well known that every graph on $ n $ vertices and $ m $ edges admits a bipartition of size at least $ m/2 $. This bound can be improved to $ m/2 + (n-1)/4 $ for connected graphs, and $ m/2 + n/6 $ for graphs without isolated vertices, as proved by Edwards, and Erdös, Gyárfás, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree $ o(n) $ in fact admit a bisection which asymptotically achieves the above bounds.These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollobás and Scott on judicious bisections of graphs.Joint work with Po-Shen Loh and Benny Sudakov