Computer Science/Discrete Mathematics Seminar II

A common way for lower bounding the expansion of a graph is by looking the second smallest eigenvalue of its Laplacian matrix. Also known as the easy direction of Cheeger's inequality, this bound becomes too weak when the expansion is \(o(1)\). In 2004, Arora, Rao and Vazirani proved the existence of "expander flows", which are certificates of graph expansion up to a factor of \(O(\sqrt{\log n})\). In this talk, I will describe a generalization of these for small set, "small set expander (SSE) flows", and I will describe an application of such flows for finding near optimal sparse cuts on graphs with certain isoperimetric profiles. This is joint work with Sanjeev Arora and Rong Ge.