Yun-Peng Li

A polylogarithmic higher-order Cheeger inequality

Let $\lambda_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph, and let $\rho_G(k)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove \[ \rho_G(k)\le C[1+\log(k+1)]^5\sqrt{\lambda_k(G)} \] for an absolute constant $C$. The constructi...