Many Sparse Cuts via Higher Eigenvalues

Anand Louis, Prasad Raghavendra, Prasad Tetali +1

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. conductance) is bounded as follows: \[ ϕ(S) \defeq \fra…