In the previous lecture we outlined a proof that if the normalized Laplacian matrix of a graph has k eigenvalues smaller than epsilon, then there are k disjoint subsets of vertices each of expansion at most O(k^2 * epsilon^1/2 ). Via dimension-reduction techniques, we show that it is also possible to find 0.99*k disjoint subsets of vertices, each of expansion at most O( (epsilon * log k)^1/2 ), which is a tight result.

This lecture describes joint work with James Lee and Shayan Oveis Gharan.