Lagmental Vicfred

Cheeger's Inequality Links Expansion to the Spectral Gap by Vicfred

tags: mathematics, spectral graph theory, random walks, electrical networks

For a normalized Laplacian, conductance and the second eigenvalue control one another. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

The mathematical object

The graph Laplacian \(L=D-A\) is positive semidefinite and turns combinatorial connectivity into linear algebra. A random walk uses \(P=D^{-1}A\) when degrees are positive.

$$ \Phi(G)=\min_{0<\operatorname{vol}(S)\le\operatorname{vol}(V)/2}\frac{|E(S,V\setminus S)|}{\operatorname{vol}(S)} $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ \frac{\lambda_2}{2}\le\Phi(G)\le\sqrt{2\lambda_2} $$

One explicit computation

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ \mathcal L=I-D^{-1/2}AD^{-1/2},\qquad0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n\le2 $$

Why the identity matters

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad \Phi(G)=\min_{0<\operatorname{vol}(S)\le\operatorname{vol}(V)/2}\frac{|E(S,V\setminus S)|}{\operatorname{vol}(S)},\\[5pt] \mathsf{C}\;&:\quad \frac{\lambda_2}{2}\le\Phi(G)\le\sqrt{2\lambda_2}. \end{aligned} $$

Where it can fail

Normalized and unnormalized Laplacians have different eigenvalues and orthogonality measures. Formulas must state which one is being used.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \frac{\lambda_2}{2}\le\Phi(G)\le\sqrt{2\lambda_2} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Sat 11 February 2012. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.