A linear Cheeger inequality using eigenvector norms

The Cheeger constant, $h_G$, is a measure of expansion within a graph. The classical Cheeger Inequality states: $\lambda_1 / 2 \leq h_G \leq \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 Inequality 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$.

Keywords

spectral graph theory, graph partitioning, Cheeger constant, graph Laplacian

2010 Mathematics Subject Classification

Primary 05C50. Secondary 05C40, 05C85.

Full Text (PDF format)

Published 4 June 2015