Expansion and Cheeger inequality - Spectral Graph Theory

Consider

𝟙_{S} : V \to ℝ

, where

𝟙_{S} (x) = 1

x \in S

and

𝟙_{S} (x) = 0

otherwise. Then

Lemma 3.5. Assuming that:

$M$ is symmetric positive semi-definite
$⟨ f, g ⟩ = 0$

Then

q_{M} (f + g) \leq 2 \max {q_{M} (f), q_{M} (g)} .

Proof. Let $λ_{i}$ , $φ_{i}$ such that $f = \sum_{i} λ_{i} φ_{i}$ and $g = \sum_{i} β_{i} φ_{i}$ . Then

q_{M} (f + g) = \frac{\sum_{i} λ_{i} {(α_{i} + β_{i})}^{2}}{∥ f + g ∥^{2}} \leq \frac{\sum_{i} λ_{i} (2 α_{i}^{2} + 2 β_{i}^{2})}{∥ f ∥^{2} + ∥ g ∥^{2}} .

Then

\begin{array}{l} q_{M} (f + g) & \leq 2 (\frac{\sum_{i} λ_{i} α_{i}^{2} + \sum_{i} λ_{i} β_{i}^{2}}{∥ f ∥^{2} + ∥ g ∥^{2}}) \\ = 2 (\frac{q_{M} (f) ∥ f ∥^{2} + q_{M} (g) ∥ g ∥^{2}}{∥ f ∥^{2} + ∥ g ∥^{2}}) \\ \leq 2 \max {q_{M} (f), q_{M} (g)} □ \end{array}

Proof of left inequality in Cheeger’s inequality. $λ_{2} \leq 2 \max {Φ (S), Φ (V ∖ S)} = 2 Φ (S, V ∖ S)$ . Then minimise over all $S$ , to get $λ_{2} \leq 2 Φ (G)$ . □

Fiedler’s Algorithm

Lemma 3.6. Assuming that:

$ψ : V \to ℝ$
$⟨ ψ, 1 ⟩ = 0$
let $(S, V ∖ S) = Fiedler (G, ψ)$

Then

Φ (S, V ∖ S) \leq \sqrt{2 q_{{\tilde{L}}_{G}} (ψ)} .

ψ : V \to ℝ

, call a cut

({x : ψ (x) \geq τ)}, {x : ψ (x) < τ})

a threshold cut for

ψ

Lemma 3.7. Assuming that:

$φ : V \to ℝ$
$⟨ φ, 1 ⟩ = 0$

Then there is

ψ : V \to ℝ_{\geq 0}

such that

q_{{\tilde{L}}_{G}} (ψ) \leq q_{{\tilde{L}}_{G}} (ψ)

| supp ψ | = | {x : ψ (x) > 0} | \leq \frac{| V |}{Q}

and any threshold cut for

ψ

is a threshold cut for

φ

Proof of Lemma 3.7. If $⟨ φ, 1 ⟩ = 0$ then

\begin{array}{l} q_{{\tilde{L}}_{G}} (φ + α 1) & = \frac{Q_{{\tilde{L}}_{G}} (φ + α 1)}{∥ φ + α 1 ∥^{2}} \\ = \frac{Q_{{\tilde{L}}_{G}} (φ)}{∥ φ ∥^{2} + α^{2}} \\ \leq \frac{Q_{{\tilde{L}}_{G}} (φ)}{∥ φ ∥^{2}} \\ = q_{{\tilde{L}}_{G}} (φ) \end{array}

Let $m \in ℝ$ be the median of $φ$ .

\begin{array}{l} | {x \in V : φ (x) > m} | & \leq \frac{| V |}{2} \\ | {x \in V : φ (x) < m} | & \leq \frac{| V |}{2} \end{array}

$\bar{φ} = φ - m 1$ , $q_{{\tilde{L}}_{G}} (\bar{φ}) \leq q_{{\tilde{L}}_{G}} (φ)$ . Let $\bar{φ} = {\bar{φ}}^{+} - {\bar{φ}}^{-}$ , where ${\bar{φ}}^{+}, {\bar{φ}}^{-} : V \to ℝ_{\geq 0}$ . So

\bar{φ} (x) = {\begin{matrix} {\bar{φ}}^{+} (x) & φ (x) > m \\ - {\bar{φ}}^{-} (x) & φ (x) < m \\ 0 & φ (x) = m \end{matrix} .

Note $⟨ {\bar{φ}}^{-}, {\bar{φ}}^{+} ⟩ = 0$ .

Claim: either ${\bar{φ}}^{+}$ or ${\bar{φ}}^{-}$ suffices.

\begin{array}{l} q_{{\tilde{L}}_{G}} (φ) & \geq q_{{\tilde{L}}_{G}} (\bar{φ}) \\ = q_{{\tilde{L}}_{G}} ({\bar{φ}}^{+} - {\bar{φ}}^{-}) \\ = \frac{\sum_{x \sim y} {({\bar{φ}}^{+} (x) - {\bar{φ}}^{-} (x) - {\bar{φ}}^{+} (y) + {\bar{φ}}^{-} (y))}^{2}}{∥ {\bar{φ}}^{+} - {\bar{φ}}^{-} ∥^{2}} \\ = \frac{\sum_{x \sim y} (({\bar{φ}}^{+} (x) - {\bar{φ}}^{+} (y)) - {({\bar{φ}}^{-} (x) - {\bar{φ}}^{-} (x))}^{2}}{∥ {\bar{φ}}^{+} ∥^{2} + ∥ {\bar{φ}}^{-} ∥^{2}} \\ \geq \frac{\sum_{x \sim y} {({\bar{φ}}^{+} (x) - {\bar{φ}}^{+} (y))}^{2} + {({\bar{φ}}^{-} (x) - {\bar{φ}}^{-} (y))}^{2}}{∥ {\bar{φ}}^{+} ∥^{2} + ∥ {\bar{φ}}^{-} ∥^{2}} \\ = \frac{q_{{\tilde{L}}_{G}} ({\bar{φ}}^{+}) ∥ \bar{φ} ∥^{2} + q_{{\tilde{L}}_{G}} ({\bar{φ}}^{-}) ∥ {\bar{φ}}^{-} ∥^{2}}{∥ \bar{φ} ∥^{2} + ∥ {\bar{φ}}^{-} ∥^{2}} \end{array}

□

Proof of Lemma 3.8. Assume $∥ ψ ∥_{\infty} = 1$ . We find $0 < t \leq 1$ . Choose $t$ at random, such that $t^{2} \sim Unif ([0, 1])$ . Let

S_{t} = {x \in V : ψ (x) > t} .

Then

𝔼 | S_{t} | = \sum_{x} ℙ (x \in S_{t}) = \sum_{x} ℙ (ψ {(x)}^{2} > t^{2}) = \sum_{x} ψ {(x)}^{2} .

Have

Φ (S_{t}) = \frac{e (S_{t}, V ∖ S_{t})}{d | S_{t} |} .

Also, can calculate:

\begin{array}{l} 𝔼 d | S_{t} | & = d \sum_{x} ψ {(x)}^{2} \\ 𝔼 e (S_{t}, V ∖ S_{t}) & = \sum_{x \sim y} ℙ (x y is cut by (S_{t}, V ∖ S_{t})) \\ = \sum_{x \sim y} | ψ {(x)}^{2} - ψ {(y)}^{2} | \\ = \sum_{x \sim y} | ψ (x) - ψ (y) | (ψ (x) + ψ (y)) \\ \leq \sqrt{\sum_{x \sim y} {(ψ (x) - ψ (y))}^{2}} \cdot \sqrt{\sum_{x \sim y} {(ψ (x) + ψ (y))}^{2}} \end{array}

Then

\begin{array}{l} \frac{𝔼 e (S_{t}, V ∖ S_{t})}{𝔼 d | S_{t} |} & \leq \sqrt{q_{{\tilde{L}}_{G}} (ψ)} \cdot \sqrt{\frac{\sum_{x \sim y} {(ψ (x) + ψ (y))}^{2}}{d \sum_{x} ψ {(x)}^{2}}} \\ \leq \sqrt{2 q_{{\tilde{L}}_{G}} (ψ)} \end{array}

Now use the following fact to finish:

Fact: If $X$ and $Y$ are random variables with $ℙ (Y > 0) = 1$ , then $ℙ (\frac{X}{Y} \leq \frac{𝔼 X}{𝔼 Y})$ .

(Proof: let $R = \frac{𝔼 X}{𝔼 Y}$ . Then $𝔼 (X - R Y) = 0$ , so $ℙ (X - R Y \leq 0)) > 0$ , hence $ℙ (\frac{X}{Y} \leq R) > 0$ ). □

Example. $C_{N}$ . This has $λ_{2} ({\tilde{L}}_{C_{N}} = 𝜃 (\frac{1}{N^{2}})$ .

For $S \subseteq C_{N}$ with $| 1 \leq S | \leq \frac{1}{2} | C_{N} |$ , we have $e (S, V ∖ S) \geq 2$ . So

Φ (S) = \min_{\begin{array}{c} S \subseteq V \\ 0 < | S | < | V | ∕ 2 \end{array}} \frac{e (S, V ∖ S)}{d | S |} = \min_{1 \leq s \leq N ∕ 2} \frac{2}{2 s} ≃ \frac{2}{N} .

Compare with Cheeger’s inequality:

\frac{1}{N^{2}} < \frac{1}{N} \leq \sqrt{\frac{1}{N^{2}}} .

Example. $G = Q_{n}$ , $N = 2^{n}$ . $G = Cay ({(ℤ ∕ 2 ℤ)}^{n}, {e_{1}, \dots, e_{n}})$ . We index eigenfunctions by sets $T \subseteq [n]$ . $χ_{T} (x) = {(- 1)}^{\sum_{i \in T} x_{i}}$ , $λ_{T} = \frac{2 | T |}{n}$ .

$λ_{2}^{(} {\tilde{L}}_{Q_{n}}) = \frac{2}{n} = \frac{2}{\log N}$ .

$Φ (Q_{n}) \geq \frac{2}{2 n} = \frac{1}{n}$ . If $S \subseteq Q_{n}$ , $| S | \leq N ∕ 2$ , then

\frac{e (S, V ∖ S)}{n | S |} \geq \frac{1}{n} ⟹ e (S, V ∖ S) \geq | S | .

Harper gives a better bound:

e (S, V ∖ S) \geq | S | \log_{2} (\frac{2^{n}}{| S |}) .

By considering $S$ being half of the cube, we get

Φ (Q_{n}) = \frac{1}{n} = \frac{λ_{2} ({\tilde{K}}_{Q_{n}})}{2} .

Fiedler’s algorithm: Let $f = \sum_{i = 1}^{n} χ_{{i}}$ , ${\tilde{L}}_{Q_{n}} f = \frac{2}{n} f$ . $f (x) = \sum_{i = 1}^{n} {(- 1)}^{x_{i}} = n - 2 | x |$ .

Φ_{k} = \frac{(\binom{n}{k}) (n - k)}{n \sum_{j = 0}^{k} (\binom{n}{j})} .

$k = \frac{n}{2}$ ,

\frac{(\binom{n}{n ∕ 2}) \frac{n}{2}}{n 2^{n - 1}} = \frac{(\binom{n}{n ∕ 2})}{2^{n}} \approx \frac{1}{\sqrt{n}} .

3 Expansion and Cheeger inequality

Fiedler’s Algorithm