Continuing on our journey through expander graphs, we prove the essential Cheeger inequality. We define $e(S,T)$ as the number of edges going from $S$ to $T$. $\partial S$ is the size of the edge boundary set $E(S,V\setminus S)$. Recall that the isoperimetric number or Cheeger constant of a graph is the infimum ratio $\frac{|\partial S|}{e(S,V)}$ over all subsets $S$ of size at most $|V|/2$.
We will be thinking of $d$-regular graphs for which we have considered the notion of spectral expansion through the spectral gap of their normalized adjacency matrix $A_G$: $\lambda(G) := \max\{|\lambda_2|,|\lambda_n|\} \leq \lambda$.
The Cheeger inequality gives us a way to relate the two notions of expansion.
<aside>
Theorem The Cheeger inequality states that:
$$ \frac{1-\lambda_2}{2}\leq h(G) \leq \sqrt{2(1-\lambda_2)} $$
</aside>
Let's prove it! We'll be working off of the wonderful notes (https://cseweb.ucsd.edu/classes/sp21/cse291-g/) from Shachar Lovett's class with small changes and simplifications at some parts. The proof has two parts, one for each side of the inequality.
Let us first remember the Courant-Fischer (CF) Theorem, which gives a characterization of the spectrum in terms of Rayleigh coefficients. If $M$ is a symmetric matrix with eigenvalues $v_1\leq...\leq v_n$ and corresponding eigenvectors $\psi_1,...,\psi_n$. Then we have that:
$$ v_i = \min\limits_{\substack{||x||=1\\x^T \psi_j = 0,j<i}}x^T M x $$
Now, let's remember the Laplacian matrix of $G$ to be defined as $L = I-A_G$. Let $0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n$ be the spectrum of $L$. We know that $\mu_2 = 1-\lambda_2$ so it suffices to show that $\mu_2 \leq 2h(G)$. By CF, we have that:
$$ \mu_2 = \min\limits_{x\perp 1^n}\frac{x^TLx}{x^T x} $$
So, all we have to do is find some $x\in\mathbb{R}^n$ that satisfies $\frac{x^T L x}{x^T x} \leq 2h(G)$. We know that $h(G)$ is a minimum over all cuts, so let's define a cut $S \subset V$ and consider its indicator vector:
Now we have to do some calculations:
$$ x = 1_S= \begin{cases} 1&, \text{if } v\in S\\ 0&, \text{otherwise} \end{cases} $$
<aside>
Note
We would be remiss if we did not stand and appreciate the power of examining Laplacians through their quadratic forms. This is a very neat trick and powerful tool for interpreting $ $L$. Specifically, we can write all quadratic forms as:
$$ x^T L x = \sum\limits_{(u,v) \in E}w_{uv}(x_u-x_v)^2 $$
It just so happens here that $w_{uv} = \frac{1}{d}$ for all edges.
</aside>
So then $\frac{x^T L x}{x^T x} = \frac{|\partial S|}{|S|}$. We're on the right track! Recall that $h(G) = h(S) = \frac{|\partial S|}{e(S,V)}$ for some $S$ and we have that $e(S,V) = d|S|$. We'll have to change $x$ a little. Of course, we have another constraint to satisfy: we must not forget that the $x$ we choose must be orthogonal to $1^n$. To do this, define:
$$ x_S= \begin{cases} 1-\frac{|S|}{n}&, \text{if } v\in S\\ -\frac{|S|}{n}&, \text{otherwise} \end{cases} $$
So we just subtract $\frac{|S|}{n}$ from $1_S$. Now, what happens? Let's try to go through the calculations again: