A Schur Complement Cheeger Inequality

Aaron Schild

Cheeger's inequality shows that any undirected graph $G$ with minimum nonzero normalized Laplacian eigenvalue ${\lambda }_G$ has a cut with conductance at most $O(\sqrt{{\lambda }_G})$. Qualitativel…