KAIST Discrete Math Seminar

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 contain 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 (CMU) and Benny Sudakov (UCLA)