The Cheeger-Alon-Milman inequality

May 14, 2008

The Cheeger-Alon-Milman inequality

Filed under: Math — Tags: eigenvalues, Sparsest cut, Spectral geometry — James Lee @ 2:37 am

Recently, Luca posted on Cheeger’s inequality. Whenever I try to reconstruct the proof, I start with the coarea formula and then play around with Cauchy-Schwarz (essentially the way that Cheeger proved it). The proof below turned out to be a bit more complicated than I thought. Oh well…

Let $G = (V,E)$ be a graph with maximum degree $d_{\max}$ and $n = |V|$ . Let’s work directly with the sparsity $\displaystyle \alpha_G = \min_{S \subseteq V} \frac{e(S,\bar S)}{|S| |\bar S|}$ which is a bit nicer. Notice that $\alpha_G n$ is within factor 2 of the Cheeger constant $h_G$ . We start with a very natural lemma:

Coarea lemma: For any $f : V \to \mathbb R$ , we have $\sum_{ij \in E} |f(i)-f(j)| \geq \alpha_G \sum_{i,j \in V} |f(i)-f(j)|$ .

Proof: Let $V_r = \{ i : f(i) \leq r \}$ , then we can write $\sum_{ij \in E} |f(i)-f(j)|$ as the integral

$\displaystyle \int_{-\infty}^{\infty} e(V_r, \bar V_r) dr \geq \alpha_G \int_{-\infty}^{\infty} |V_r| |\bar V_r|dr = \alpha_G \sum_{i,j \in V} |f(i)-f(j)|$

Now a bit of spectral graph theory: $L = D - A$ is the Laplacian of $G$ , where $D$ is the diagonal degree matrix and $A$ is the adjacency matrix. The first eigenvalue is $\lambda_1 = 0$ and the first eigenvector is $(1,1,\ldots,1)$ . If $\phi : V \to \mathbb R$ is the second eigenvector, then the second eigenvalue can be written

$\displaystyle \lambda_2 = \frac{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}{\sum_{i \in V} \phi(i)^2} \quad(1)$

Given (1), it is natural to apply the coarea formula with $f(i) = \phi(i)^2$ and then play around.

Theorem: $\displaystyle \lambda_2 \geq \frac{\alpha_G^2 n^2}{32 d_{\max}}$

Proof: Unfortunately, if we try $f(i) = \phi(i)^2$ , it doesn’t quite work (think of the case when $\phi$ takes some value $v$ and $-v$ equally often). Instead, let’s eliminate this case by setting $\phi_0(i) = \max(m,\phi(i))$ , where $m = \mathrm{med}(\phi)$ . Now applying the coarea lemma with $f(i) = \phi_0(i)^2$ yields:

$\displaystyle \alpha_G \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| \leq \sum_{ij \in E} |\phi_0(i)^2-\phi_0(j)^2|$

$\displaystyle = \sum_{ij \in E} |\phi_0(i)+\phi_0(j)||\phi_0(i)-\phi_0(j)| \leq \sqrt{\sum_{ij \in E} [\phi_0(i)+\phi_0(j)]^2} \sqrt{\sum_{ij \in E} |\phi_0(i)-\phi_0(j)|^2}$

$\displaystyle \leq \sqrt{2 d_{\max}} \sqrt{n m^2 + \sum_{i \in V} \phi(i)^2} \sqrt{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}\quad\quad (2)$

Notice that the same inequality holds for $\phi_1(i) = \min(m, \phi(i))$ . Also, observe that

$\displaystyle \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| + |\phi_1(i)^2-\phi_1(j)^2|$

$\displaystyle \geq \frac{n}{2} \sum_{i : \phi(i) \geq m} [\phi(i)-m]^2 + \frac{n}{2} \sum_{i : \phi(i) \leq m} [\phi(i)-m]^2$

$\displaystyle = \frac{n}{2} \sum_{i \in V} [\phi(i)-m]^2 = \frac{n}{2} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right]$ ,

where in the final line we have used the fact that $\sum_{i \in V} \phi(i) = 0$ since $\phi$ is orthogonal to the first eigenvector.

So we can assume that $\displaystyle \sum_{i,j \in V} |\phi_0(i)-\phi_0(j)|^2 \geq \frac{n}{4} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right]$ . Plugging this into (2), rearranging, and using (1) yields the claim.

About these ads

Comments (2)

2 Comments »

[...] group in terms of on . But on a small, connected graph cannot be too close to zero by the discrete Cheeger inequality. In this way, we arrive at a contradiction if the image of the action is too small. Theorem 2 [...]

Pingback by Eigenvalue multiplicity and growth of groups « tcs math - some mathematics of theoretical computer science — June 15, 2008 @ 9:25 am
[...] For the proof, I’ll refer to Theorem 4 in Alon-Klartag. Note that the proof for the Dirichlet version is even simpler than for the “standard” (Neumann) eigenvalues—it’s just a straightforward combination of Cauchy-Schwarz and the coarea formula. [...]

Pingback by Lecture 2: Spectral partitioning and near-optimal foams « tcs math - some mathematics of theoretical computer science — September 26, 2008 @ 2:12 am

RSS feed for comments on this post. TrackBack URI

	Nguyen Van Phuc on No frills proof of higher-orde…
	Nguyen Van Phuc on No frills proof of higher-orde…
	Nguyen Van Phuc_Viet… on No frills proof of higher-orde…
	Nguyen Van Phuc_Viet… on No frills proof of higher-orde…
	http://iwriteadirtyb… on Expanders from the action of…

tcs math – some mathematics of theoretical computer science

May 14, 2008

The Cheeger-Alon-Milman inequality

Like this:

2 Comments »

Leave a Reply Cancel reply

Recent Comments

Recent Posts

Links

Math & TCS blogs

Top Posts

Archives

Follow “tcs math - some mathematics of theoretical computer science”