A Linear Cheeger Inequality using Eigenvector Norms

Abstract

The Cheeger constant, $h_G$, is a measure of expansion within a graph. The classical Cheeger Inequality states: ${\lambda }_1/2\le h_G\le \sqrt{2{\lambda }_1}$ where ${\lambda }_1$ is the first nontrivial eigenvalue of the normalized Laplacian matrix. Hence, $h_G$ is tightly controlled by ${\lambda }_1$ to within a quadratic factor. We give an alternative Cheeger Inequality where we consider the $\infty$-norm of the corresponding eigenvector in addition to ${\lambda }_1$. This inequality controls $h_G$ to within a linear factor of ${\lambda }_1$ thereby providing an improvement to the previous quadratic bounds. An additional advantage of our result is that while the original Cheeger constant makes it clear that $h_G\to 0$ as ${\lambda }_1\to 0$, our result shows that $h_G\to 1/2$ as ${\lambda }_1\to 1$.

8 pages, 2 figures