Eigenvalue bounds, spectral partitioning, and metrical deformations via flows

Punyashloka Biswal, James R. Lee, Satish Rao

We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed t…