DIMACS - Graduate Student Combinatorics Seminar

Title: An upper bound on the bisection width of regular graphs

Speaker: Dev Desai, Rutgers University

Date: Wednesday, December 9, 2009 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


The 'bisection width' of a graph is defined as the minumum number of edges than need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large. In this talk, I will present a result of Noga Alon's, which gives an upper bound on the bisection width of any d-regular graphs, when the number of vertices is 'much more' than d. Time permitting, I will also discuss some other interesting cut problems and what we know about them.