A Linear Cheeger Inequality using Eigenvector Norms

Original · EN

The Cheeger constant, hG, is a measure of expansion within a graph. The classical Cheeger Inequality states: λ₁/2 ≤ hG ≤ √2 λ₁ where λ₁ is the first nontrivial eigenvalue of the normalized Laplacian matrix. Hence, hG is tightly controlled by λ₁ to within a quadratic factor. We give an alternative Cheeger Inequality where we consider the ∞-norm of the corresponding eigenvector in addition to λ₁. This inequality controls hG to within a linear factor of λ₁ 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 hG → 0 as λ₁ → 0, our result shows that hG → 1/2 as λ₁ → 1.