printable pdf
比利时vs摩洛哥足彩 ,
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

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