##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Choong-Bum Lee

#### UCLA

## Large and judicious bisections of graphs

##### Abstract:

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\H{o}s, Gy\'arf\'as, 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\'as and Scott on judicious bisections of graphs. Joint work with Po-Shen Loh and Benny Sudakov

### June 7, 2011

### 4:00 PM

### AP&M 7321

****************************