Loewner order - Spectral Graph Theory

4 Loewner order

Definition 4.1 (Loewner order). For $A$ , $B$ matrices, write $A ≼ B$ if $B - A$ is positive semidefinite. In particular, $A ≽ 0$ if and only if $A$ is positive semidefinite.

$q_{A} (f) = \frac{⟨ f, A f ⟩}{⟨ f, f ⟩} = 0$ .

$A ≼ B$ if and only if $\forall f \neq 0$ ,

\frac{⟨ f, A f ⟩}{⟨ f, f ⟩} \leq \frac{⟨ f, B f ⟩}{⟨ f, f ⟩} .

$⟨ f, A f ⟩ \leq ⟨ f, B f ⟩$ .

This is indeed an order: $A ≼ B ≼ C$ implies $A ≼ C$

⟨ f, A f ⟩ \leq ⟨ f, B f ⟩ \leq ⟨ f, C f ⟩ .

If $A ≼ B$ , then $λ_{k} (A) \leq λ_{k} (B)$ .

λ_{k} (A) = \min_{\dim W = k} \max_{\begin{array}{c} f \in W \\ f \neq 0 \end{array}} \frac{⟨ f, A f ⟩}{⟨ f, f ⟩} .

$A ≼ B$ if and only if $A + C ≼ B + C$ .

If $G$ is a graph, then $L_{G} ≼ 0$ .

Definition 4.2 (eps-approximation). $G$ is an $𝜀$ -approximation of $H$ if

(1 - 𝜀) L_{H} ≼ L_{G} ≼ (1 + 𝜀) L_{H} .

Lemma 4.3. Given the definition $∥ M ∥ = \max_{f \neq 0} \frac{∥ M f ∥}{∥ f ∥}$ (for $M$ symmetric), we have $∥ M ∥ = \max {| λ_{k} (M) |}$ .

Proof. $f = \sum_{i} α_{i} φ_{i}$ , $M φ_{i} = λ_{i} φ_{i}$ , $∥ f ∥^{2} = \sum_{i} α_{i}^{2}$ ,

∥ M f ∥^{2} = {∥ \sum_{i} α_{i} λ_{i} φ_{i} ∥}^{2} = \sum_{i} α_{i}^{2} λ_{i}^{2} .

\frac{∥ M f ∥}{∥ f ∥} = \sqrt{\frac{\sum_{i} α_{i}^{2} λ_{i}^{2}}{\sum_{i} α_{i}^{2}}} \leq \max_{k} | λ_{k} | . □

Lemma 4.4. Assuming: - $G$ is an $𝜀$ -approximation of $H$ Then: $∥ L_{G} - L_{H} ∥ \leq 𝜀$ .

Proof. $- 𝜀 {\tilde{L}}_{H} ≼ {\tilde{L}}_{G} - {\tilde{L}}_{H} ≼ 𝜀 {\tilde{L}}_{H}$ . $λ_{k} ({\tilde{L}}_{G} - {\tilde{L}}_{H}) \leq λ_{k} ({\tilde{L}}_{H}) \leq 2 𝜀$ . □

Definition ((d,eps)-expander). $G = (V, E)$ , $| V | = n$ is a $(d, 𝜀)$ -expander if $G$ is an $𝜀$ -approximation of $\frac{d}{n} K_{n}$ .

Equivalent:

(1 - 𝜀) \frac{d}{n} L_{K_{n}} ≼ L_{G} ≼ (1 + 𝜀) \frac{d}{n} L_{K_{n}} .

$L_{K_{n}} = (n - 1) I - A_{K_{n}} = n I - J$ , where $J$ is the all ones matrix ( $J (x, y) = 1$ ). If $f ⊥ q$ , then $J f = ⟨ f, 1 ⟩ f = 0$ . In this case, $L_{K_{n}} f = n I f - J f = n f$ .

So $λ_{k} (L_{K_{n}}) = n$ for $k \geq 0$ .

(1 - 𝜀) \frac{d}{n} (n I - J) ≼ d I - A_{G} ≼ (1 + 𝜀) \frac{d}{n} (n I - J)

- 𝜀 \frac{2}{n} (n I - J) ≼ d I - A_{G} - \frac{d}{n} (n I - J) ≼ 𝜀 \frac{d}{n} (n I - J)

- 𝜀 (d I - \frac{d}{n} J) ≼ \frac{d}{n} J - A_{G} ≼ 𝜀 (d I - \frac{d}{n} J)

For $f ⊥ 1$ , $- 𝜀 d ⟨ f, f ⟩ \leq - ⟨ f, A f ⟩ \leq 𝜀 d ⟨ f, f ⟩$ .

So $G$ is a $(d, 𝜀)$ -expander if and only if

| λ_{k} (A_{G}) | \leq 𝜀 d

for all $1 \leq k \leq n - 1$ .

Lemma 4.5 (Expander Mixing Lemma). Assuming that:

$G$ is $d$ -regular
$G$ is a $(d, 𝜀)$ -expander

Then

\forall S, T \subseteq V

| e (S, T) - \frac{d}{n} | S | | T | | \leq \frac{𝜀 d}{n} \sqrt{| S | | T | | S^{c} | | T^{c} |} .

Proposition 4.6. Assuming that:

$G$ a $d$ -regular graph on $n$ vertices
$λ, 𝜀 > 0$ , $𝜀 d = λ$

Then the following are equivalent:

(i) $G$ is a $(n, d, λ)$ -graph
(ii) $λ_{k} (A_{G}) ∋ [- λ, λ]$ , for $1 \leq k \leq n - 1$
(iii) $λ_{k} (L_{G}) \in [d - λ, d + λ]$ for $2 \leq k \leq n$
(iv) $λ_{k} ({\tilde{L}}_{G}) \in [1 - \frac{λ}{d}, 1 + \frac{λ}{d}] = [1 - 𝜀, 1 + 𝜀]$ for $1 \leq k \leq n$
(v) $(1 - 𝜀) \frac{d}{n} L_{K_{n}} ≼ L_{G} ≼ (1 + 𝜀) \frac{d}{n} L_{K_{n}}$
(vi) $G$ is $(d, 𝜀)$ -expander (also $(d, \frac{λ}{d})$ -expander)
(vii) $∥ L_{G} - \frac{d}{n} L_{K_{n}} ∥ \leq 𝜀 d = λ$
(viii) $∥ A_{G} - \frac{d}{n} J ∥ \leq 𝜀 d = λ$

Lemma 4.7 (Expander Mixing Lemma). Assuming that:

$G = (V, E)$ an $(n, d, λ)$ -graph
$S, T \subseteq V$ (and define $e (S, T) = \sum_{x \in S} \sum_{y \in T} 𝟙_{x y \in E}$ )

Then

\begin{array}{l} | e (S, T) - \frac{d}{n} | S | | T | | & \leq \frac{λ}{n} \sqrt{| S | | S^{c} | | T | | T^{c} |} \\ \leq λ \sqrt{| S | | T |} \end{array}

Proof. $⟨ 𝟙_{S}, L_{G} 𝟙_{T} ⟩ = ⟨ 𝟙_{S}, (d I - A_{G}) 𝟙_{T} ⟩$ , $⟨ 𝟙_{S}, d I 𝟙_{T} ⟩ = d | S \cap T |$ .

\begin{array}{l} ⟨ 𝟙_{S}, A_{G} 𝟙_{T} ⟩ & = \sum_{x} \sum_{y} 𝟙_{S} (x) A_{G} (x, y) 𝟙_{T} (y) \\ = \sum_{x} \sum_{y} 𝟙_{x y \in E} \\ = e (S, T) \end{array}

$\frac{d}{n} L_{K_{n}} = d I - \frac{d}{n} J$ .

⟨ 𝟙_{S}, \frac{d}{n} J 𝟙_{T} ⟩ = \frac{d}{n} ⟨ 𝟙_{S}, J 𝟙_{T} ⟩ = \frac{d}{n} \sum_{x} \sum_{y} J (x, y) = \frac{d}{n} | S | | T | .

\begin{array}{l} | e (S, T) - \frac{d}{n} | S | | T | | & = | ⟨ 𝟙_{S}, (\frac{d}{n} L_{K_{n}} - L G) 𝟙_{T} ⟩ | \\ \leq ∥ 𝟙_{S} ∥ ∥ (\frac{d}{n} L_{K_{n}} - L_{G}) 𝟙_{T} ∥ \\ \leq ∥ 𝟙_{S} ∥ ∥ (\frac{d}{n} L_{K_{n}} - L_{G}) ∥ ∥ 𝟙_{T} ∥ \\ \leq λ ∥ 𝟙_{S} ∥ ∥ 𝟙_{T} ∥ \\ = λ \sqrt{| S | | T |} \end{array}

To get the better bound, we should consider functions which are perpendicular to

1

: balanced function

f_{S} = 𝟙_{S} - \frac{| S |}{n} 1

$L_{G} f_{S} = L_{G} (𝟙_{S} - α) = L 𝟙_{S}$ .

\begin{array}{l} | e (S, T) - \frac{d}{n} | S | | T | | & = | ⟨ f_{S}, (\frac{d}{n} L_{K_{n}} - L_{G}) f_{T} ⟩ | \\ \leq λ ∥ f_{S} ∥ ∥ f_{T} ∥ \end{array}

\begin{array}{l} ∥ f_{S} ∥^{2} & = | S | {(1 - \frac{| S |}{n})}^{2} + (n - | S |) {(- \frac{| S |}{n})}^{2} \\ = | S | (1 - \frac{2 | S |}{n} + \frac{| S |^{2}}{n^{2}}) + (n - | S |) \frac{| S |^{2}}{n^{2}} \\ = | S | - \frac{2 | S |^{2}}{n} + \frac{| S |^{3}}{n^{2}} + \frac{| S |^{2}}{n} - \frac{| S |^{3}}{n^{2}} \\ = | S | - \frac{| S |^{2}}{n} \\ = \frac{n | S | - | S |^{2}}{n} \\ = \frac{| S | | S^{c} |}{n} \end{array}

| e (S, T) - \frac{d}{n} | S | | T | | \leq \sqrt{| S | | S^{c} | | T | | T^{c} |} . □

If $G$ is an $(n, d, λ)$ -graph and $I \subseteq V$ an independent set, then

0 = e (I, I) \geq \frac{d}{n} | I |^{2} - \frac{λ}{n} | I | | I^{c} | .

$λ | I | | I^{c} | \geq d | I |^{3}$ .

| I | \leq \frac{λ}{d} | I^{c} | = \frac{λ}{d} (n - | I |) .

(1 + \frac{λ}{d}) | I | \leq \frac{λ}{d} n

| I | \leq \frac{λ}{d (1 + \frac{λ}{d})} n = \frac{λ}{d + λ} n .

Hoffman bound: $α (G) \leq \frac{λ}{d + λ} n$ .

Fix $d$ . How small can $λ$ be such that there is an infinite family $G_{n}$ of $(n, d, λ)$ -graphs?

Note $A_{G}^{2}$ has $d$ in each entry of the diagonal, so

Tr A_{G}^{2} = d n = \sum_{i} λ_{i} (A_{G}^{2}) = \sum_{i} {(λ_{i} (A_{G}))}^{2} .

So $d n \leq d^{2} + (n - 1) λ^{2}$ .

So $(n - 1) λ^{2} \geq d n - d^{2} = d (n - d)$ , so

λ^{2} \geq \frac{d (n - d)}{n - 1} = d (\frac{n - 1 - (d - 1)}{n - 1}) = d (1 - \frac{d - 1}{n - 1}) .

$λ \geq \sqrt{d} (1 - o (1))$ as $n \to \infty$ .

Alon-Boppana Theorem: $λ \geq 2 \sqrt{d - 1} - o (1)$ .

Claim: There exist families of $(n, d, λ)$ -graphs with $λ = 2 \sqrt{d - 1}$ . They are called Ramanujan graphs. We will probably not prove existence of these.

Call $𝜀$ -Ramanujan if $λ \geq 2 \sqrt{d - 1} + 𝜀$ .

Theorem 4.8 (Friedman). Assuming: - $𝜀 > 0$ , $n \to \infty$ Then:

ℙ (random d -regular graph on n vertices is 𝜀 -Ramanujan) \to 1 .

Maxcut in $(n, d, λ)$ -graph:

\begin{array}{l} e (S, S^{c}) & \leq \frac{d}{n} | S | | S^{c} | + \frac{λ}{n} | S | | S^{c} | \\ \leq (\frac{d}{n} + \frac{λ}{n}) \frac{n^{2}}{4} \\ = \frac{d n}{4} + \frac{λ n}{4} \\ \leq \frac{e (G)}{2} + \frac{λ n}{4} \end{array}

Diameter, vertex expansion. $S \subseteq V$ , $\partial S = {x \in S^{c} : x \sim S}$ .

\frac{| \partial S |}{| S |} \geq \frac{e (S, S^{c})}{d | S |} = Φ (S) \geq \frac{λ_{2} ({\tilde{L}}_{G})}{2} \geq \frac{(1 - \frac{λ}{d})}{2}

$| \partial S | \geq (\frac{1 - λ ∕ d}{2}) | S |$ .

Exercise: Diameter $O (\log n)$ .

Vertex expansion

$(n, d, λ)$ -graph $G = (V, E)$ . Have for all $S, T \subseteq V$ ,

| e (S, T) - \frac{d}{n} | S | | T | | \leq \frac{λ}{n} \sqrt{| S | | S^{c} | | T | | T^{c} |} .

$Φ_{v} (S) = \frac{| \partial S |}{| S |}$ .

\begin{array}{l} | \partial S | & \geq \frac{e (S, S^{c})}{d} \\ Φ_{v} (S) & \geq \frac{e (S, S^{c})}{d | S |} \\ = Φ_{e} (S) \end{array}

S \subseteq V

| S | \leq n ∕ 2

, then

\begin{array}{l} Φ_{V} (S) & \geq Φ_{e} (G) \\ \geq \frac{λ_{2} ({\tilde{L}}_{G})}{2} \\ Φ_{v} (S) & \geq \frac{(1 - \frac{λ}{d})}{2} \\ | S \cup \partial S | & \geq (1 + \frac{1}{2} - \frac{λ}{2 d}) \end{array}

$n \to \infty$ , $d$ , $λ$ fixed. $λ \leq d - δ$ , $δ > 0$ . $| S \cup \partial S | \geq (1 + κ) | S |$ for some $κ > 0$ . Hence

| B (x, r) | \geq {(1 + κ)}^{r}

if $| B (x, r - 1) | \leq n ∕ 2$ .

$diam G = O_{\frac{λ}{d}} (\log n)$ (by considering ball around start and end).

Why aren’t Cayley graphs of abelian groups expanders?

Let $Γ$ be an abelian group and $S \subseteq Γ$ a set of generators of size $d$ . Let $| Γ | = n \to \infty$ . Let $G = Cay (Γ, S)$ . Then

| B (x, r) | \leq {(2 r + 1)}^{d} .

This is not exponential in $r$ , so the Cayley graph can’t be an expander.

Theorem 4.9 (Alon-Boppana). Assuming that:

$G = (V, E)$ an $(n, d, λ)$ -graph

Then as

n \to \infty

λ \geq 2 \sqrt{d - 1} - O (1) .

Proof 1. Pick edge $s t$ , pick $r \in ℤ_{\geq 0}$ .

$φ : V \to ℝ$ ,

φ (x) = {\begin{matrix} {(d - 1)}^{- i ∕ 2} & if x \in V_{i}, i \leq r \\ 0 & if x \in V_{i}, i > r \end{matrix}

q_{L} (φ) = \frac{⟨ φ, L φ ⟩}{⟨ φ, φ ⟩} ⟨ φ, φ ⟩ = \sum_{i = 0}^{r} \frac{| V_{i} |}{{(d - 1)}^{i}} .

\begin{array}{l} ⟨ φ, L φ ⟩ & = \sum_{x \sim y} {(φ (x) - φ (y))}^{2} \\ = \sum_{i = 0}^{r - 1} e (V_{i}, V_{i + 1}) {(\frac{1}{{(d - 1)}^{i ∕ 2}} - \frac{1}{{(d - 1)}^{(i + 1) ∕ 2}})}^{2} + \frac{e (V_{r}, V_{r + 1})}{{(d - 1)}^{r}} \\ = \sum_{i = 0}^{r - 1} \frac{e (V_{i}, V_{i + 1})}{{(d - 1)}^{i}} {(1 - \frac{1}{\sqrt{d - 1}})}^{2} + \frac{e (V_{r}, V_{r + 1})}{{(d - 1)}^{r}} \end{array}

e (V_{i}, V_{i + 1}) \leq (d - 1) | V_{i} |

\begin{array}{l} ⟨ φ, L φ ⟩ & \leq \sum_{i = 0}^{r - 1} \frac{| V_{i} |}{{(d - 1)}^{i}} {(\sqrt{d - 1} - 1)}^{2} + \frac{| V_{r} |}{{(d - 1)}^{r}} (d - 1) \\ {(\sqrt{d - 1} - 1)}^{2} & = (d - 1) - 2 \sqrt{d - 1} + 1 = d - 2 \sqrt{d - 1} \\ ⟨ φ, L φ ⟩ & \leq (d - 2 \sqrt{d - 1}) \sum_{i = 0}^{r - 1} \frac{| V_{i} |}{{(d - 1)}^{i}} + (d - 1) \frac{| V_{r} |}{{(d - 1)}^{r}} \\ | V_{r} | & \leq (d - 1) | V_{r - 1} | \leq \dots \leq {(d - 1)}^{r - i} | V_{i} | \\ ⟹ \frac{| V_{r} |}{{(d - 1)}^{r}} & \leq \frac{1}{r} \sum_{i = 0}^{r} \frac{| V_{i} |}{{(d - 1)}^{i}} \\ ⟨ φ, L φ ⟩ & \leq (d - 2 \sqrt{d - 1}) \sum_{i = 0}^{r} \frac{| V_{i} |}{{(d - 1)}^{i}} + (2 \sqrt{d - 1}) \frac{| V_{r} |}{{(d - 1)}^{r}} \\ \leq (d - 2 \sqrt{d - 1} + \frac{2 \sqrt{d - 1} - 1}{r + 1}) ⟨ φ, φ ⟩ \\ ⟹ λ_{2} (L) & = \min_{\dim W = 2} \max_{\begin{array}{c} f \in W \\ f \neq 0 \end{array}} \frac{⟨ f, L f ⟩}{⟨ f, f ⟩} \end{array}

Suppose $G$ has 2 deges at distance $> 2 r + 2$ .

$f$ , $f^{'}$ as above. $⟨ f, f^{'} ⟩ = 0$ .

Q_{L} (α f + β f^{'}) = Q_{L} (α f) + Q_{L} (β f^{'}) .

Let $W = span {f, f^{'}}$ .

\begin{array}{l} λ_{2} (L) & \leq \max_{(α, β) \neq (0, 0)} \frac{Q_{L} (α f + β f^{'})}{∥ α f + β f^{'} ∥} \\ \leq \frac{α^{2} Q_{L} (f) + β^{2} Q_{L} (f^{'})}{α^{2} ∥ f ∥ + β^{2} ∥ f^{'} ∥} \\ \leq d - 2 \sqrt{d - 1} + \frac{2 \sqrt{d - 1} - 1}{r + 1} □ \end{array}

Corollary 4.10. For all $d$ , there are finitely many $(n, d, λ)$ -graphs with $λ < 2 \sqrt{d - 1}$ .

$r = c \log n$ .

λ_{n - 1} (A_{G}) \geq 2 \sqrt{d - 1} - O_{d} (\frac{1}{\log n}) .

For Alon-Boppana:

Proof 2. $Tr A^{2 k} = \sum_{x} A^{2 k} (x, x)$ . Note that

# {closed walks of length 2 k in G starting from x} .

is at least

# {closed walks of length 2 k in \prod_{d} starting from 0}

( $\prod_{d}$ is an infinite $d$ -regular tree). The latter is at least

{(d - 1)}^{k} \frac{1}{k + 1} (\binom{2 k}{k}) \approx {(2 \sqrt{d - 1})}^{2 k + o (1)} 2^{2 k} .

\leq \sum_{i = 1}^{n} λ_{i}^{2 k} \leq d^{2 k} + (n - 1) λ^{2 k} .

Exercise: finish details. □

$\min {| λ_{1} (A) | λ_{n - 1} (A)} \geq \dots$

4.1 One-sided expanders

Goal is to find: $G_{n}$ graphs with $n$ vertices, $d$ -regular such that $λ_{n - 1} (A_{G}) \leq λ < d$ .

Reminder: (Friedman) If $G \sim G_{n, d}$ uniform random $d$ -regular graph then

ℙ (G_{n} is (n, d, 2 \sqrt{d - 1} + 𝜀) -graph) \to 1 .

Φ (G_{n}) \geq \frac{λ_{2} ({\tilde{L}}_{G})}{2} = \frac{λ_{2} (L_{G})}{2 d} = \frac{(d - λ_{n - 1} (A_{G}))}{2 d} \geq \frac{1}{2} - \frac{𝜀}{2} > 0 .

Theorem 4.11. Assuming that:

$d = 2 l$ large enough

Then there is

𝜀 = 𝜀_{d} > 0

such that there are

d

-regular graphs (or multi-graphs)

G_{n}

n

vertices with

Φ (G_{n}) \geq 𝜀

for all sufficiently large

n

Graphs $G_{n}$ are as follows:

$V (G_{n}) = [n]$ , $d = 2 l$ .
Take $π_{1}, \dots, π_{l} : [n] \to [n]$ uniform independent permutations.
Set
$E (G_{n}) = {{x, π_{i} (x)} : x \in [n], i \in [l]} .$

Lemma 4.12. There is $c = c_{d} > 0$ such that

ℙ (G_{n} is d -regular, i.e. G_{n} is simple) \geq c - o (1) .

Lemma 4.13. If $G_{n}$ is $d$ -regular, then there exists $𝜀 = 𝜀_{d} > 0$ such that

ℙ (Φ (G_{n}) < 𝜀) \to 0 .

Proof. If $Φ (G_{n}) < 𝜀$ then there exists $F \subseteq [n]$ , $r = | F | \leq \frac{n}{2}$ , there exists $F^{'}$ , $F \subseteq F^{'}$ and $e (F, F^{'}) = d | F |$ and $| F^{'} | = r + r^{'}$ , $r^{'} = ⌊ 𝜀 r ⌋$ .

ℙ (Φ (G_{n}) < 𝜀) < \sum_{1 \leq r \leq \frac{n}{2}} \sum_{\begin{array}{c} F \subseteq F^{'} \subseteq [n] \\ | F | = r \\ | F^{'} | = r + r^{'} \end{array}} ℙ (π_{i} (F) \subseteq F^{'} for all i \in [l]) .

$ℙ (π_{1} (F) \subseteq F^{'}) = \frac{(\binom{r + r^{'}}{r})}{(\binom{n}{r})}$ .

ℙ \leq \sum_{1 \leq r \leq \frac{n}{2}} \frac{n!}{r! r^{'}! (n - r - r^{'})!} {(\frac{(\binom{r + r^{'}}{r})}{(\binom{n}{r})})}^{l} .

Fact 1: $\frac{(\binom{a}{k})}{(\binom{b}{k})} \leq {(\frac{a}{b})}^{k}$ if $a \leq b$ .

Proof: It is equivalent to

b a \cdot b (a - 1) \dots b (a - k + 1) \leq a b \cdot a (b - 1) \dots a (b - k + 1) .

Compare the product term by term.

Fact 2: $n! \geq {(\frac{n}{e})}^{n}$ . Proof:

e^{n} = \sum_{k \geq 0} \frac{n^{k}}{k!} \geq \frac{n^{n}}{n!} .

Using these:

\frac{n!}{r! r^{'}! (n - r - r^{'})!} \leq \frac{n^{r + r^{'}}}{r! r^{'}!} = \frac{n^{r + r^{'}}}{(r + r^{'})!} (\binom{r + r^{'}}{r}) \leq {(2 e)}^{r + r^{'}} {(\frac{n}{e + e^{'}})}^{r + r^{'}} .

\begin{array}{l} ℙ & \leq \sum_{1 \leq r \leq \frac{n}{2}} {(2 e)}^{r + r^{'}} {(\frac{n}{r + r^{'}})}^{r + r^{'}} {(\frac{r + r^{'}}{n})}^{l r} \\ \leq \sum_{1 \leq r \leq \frac{n}{2}} {(2 e)}^{2 r} {(\frac{(1 + 𝜀) r}{n})}^{r (l - 1 - 𝜀)} \end{array}

Decompose as $\sum_{1 \leq r \leq n ∕ 2} = \sum_{1 \leq r \leq K} + \sum_{K < r \leq n ∕ 2} = S_{1} + S_{2}$ . Choose $𝜀 > 0$ small so that $γ = \frac{1 + 𝜀}{2}$ is small. Choose $l$ large so that $γ^{l - 1 - 𝜀} < \frac{1}{2 {(2 e)}^{2}}$ .

\begin{array}{l} S_{2} & \leq \sum_{K < r \leq \frac{n}{2}} {(2 e)}^{2 r} {(\frac{(1 + 𝜀)}{2})}^{r (l - 1 - 𝜀)} \\ \leq \sum_{K < r \leq \frac{n}{2}} {(\frac{1}{2})}^{r} \\ \leq \frac{1}{2^{K}} \end{array}

Now $S_{1}$ .

\begin{array}{l} S_{1} & \leq \sum_{1 \leq r \leq K} {(2 e)}^{2 r} {(\frac{(1 + 𝜀) r}{n})}^{r (l - 1 - 𝜀)} \\ \leq {(\frac{2 K}{n})}^{l - 2} \sum_{1 \leq r \leq K} {(2 e)}^{2 r} \\ \leq c^{K} {(\frac{K}{n})}^{l} \end{array}

Now let $K = \log \log \log n$ , so this is $\leq O ((\log \log n) n^{- l} {(\log \log \log n)}^{l}) \to 0$ . Also, $S_{1} \leq \frac{1}{2^{K}}$ term goes to $0$ . □

For the lemma about $ℙ (d -regular) \geq c - o (1)$ :

These are the bad things. Use Bonferroni inequalities (the partial sum of inclusion exclusion principle inequalities).

$(n, d, λ)$ -graph

$n$ : number of vertices, $d$ -regular, $λ_{k} (A) \in [- λ, λ]$ , $k \neq n$ .

Ramanujan graph: $(n, d, 2 \sqrt{d - 1})$ -graph.

Petersen $(10, 3, 2 \sqrt{2})$ -graph.
Complete (bipartite), $d = n - 1$ big :(.
Paley $Cay (ℤ ∕ p ℤ, {x^{2} : x \in ℤ ∕ p ℤ, x \neq 0})$ , $p \equiv 1 (m o d 4)$ . $d = \frac{p - 1}{2}$ big :(.

Alon-Boppana: For every $𝜀 > 0$ fixed $d \geq 3$ , there are finitely many $(n, d, 2 \sqrt{d - 1} - 𝜀)$ -graphs.

Bipartite: $(n, d, λ)$ -graph, $n$ vertices, $d$ -regular, $λ_{k} (A) \in [- λ, λ]$ for $k \neq n, 1$ .

Theorem 4.14 (Lubotsky-Phillips-Sanak / Margoulis). Assuming that:

$p$ prime
$d = p + 1$
$n$ arbitrarily large

Then there exists a

(n, d, 2 \sqrt{d - 1})

-graph.

Goal:

Theorem 4.15 (Marcus, Spielman, Srivastava). Assuming that:

$d \geq 3$

Then there are

(n, d, 2 \sqrt{d - 1})

-bipartite graphs for arbitrarily large

n

Strategy: Bilu and Linial. Lifts of graphs:

Definition 4.16 (2-lift). A 2-lift of a graph $G = (V, E)$ is a graph $Ĝ = (\hat{V}, Ê)$ with

$x \in V$ $⟹$ $x_{0}, x_{1} \in \hat{V}$ .
$x y \in E$ $⟹$ either $x_{0} y_{0}, x_{1} y_{1} \in Ê$ or $x_{0} y_{1}, x_{1} y_{0} \in Ê$ .

(and no other vertices or edges).

Definition 4.17 (Signing). $S : V \times V \to ℝ$ is a signing of $G$ if

S (x, y) = {\begin{matrix} \pm 1 & if A (x, y) = 1 \\ 0 & if A (x, y) = 0 \end{matrix}

and $S (x, y) = S (y, x)$ (symmetric). So can think of $S$ as a function $E \to {\pm 1}$ .

$A_{S}^{+} (x, y) = A (x, y) 𝟙_{S (x, y) = 1}$ . $A_{S}^{-} (x, y) = A (x, y) 𝟙_{S (x, y) = - 1}$ . Have $A = A_{S}^{+} + A_{S}^{-}$ , $S = A_{S}^{+} - A_{S}^{-}$ .

Lemma 4.18. The eigenvalues of $Ĝ$ are the eigenvalues of $A_{G}$ (old) together with the eigenvalues of $S$ (new).

Proof.

A_{Ĝ_{S}} = (\begin{matrix} A_{S}^{+} & A S_{S}^{-} \\ A_{S}^{-} & A S_{S}^{+} \end{matrix})

Let $A φ = λ φ$ . Then

A_{Ĝ_{S}} (\begin{matrix} φ \\ φ \end{matrix}) = (\begin{matrix} A_{S}^{+} φ + A_{S}^{-} φ \\ A_{S}^{-} φ + A_{S}^{+} φ \end{matrix}) = (\begin{matrix} A φ \\ A φ \end{matrix}) = (\begin{matrix} λ φ \\ λ φ \end{matrix}) = λ (\begin{matrix} φ \\ φ \end{matrix}) .

Let $S η = μ η$ . Now

A_{Ĝ_{S}} (\begin{matrix} η \\ - η \end{matrix}) = (\begin{matrix} A_{S}^{+} η - A_{S}^{-} η \\ A_{S}^{-} η - A_{S}^{+} η \end{matrix}) = (\begin{matrix} S η \\ - S η \end{matrix}) = (\begin{matrix} μ η \\ - μ η \end{matrix}) = μ (\begin{matrix} η \\ - η \end{matrix}) . □

Conjecture 4.19 (Bilu, Linial). If $G$ is $d$ -regular, then there exists a signing $S : E (G) \to {\pm 1}$ whose eigenvalues are in $[- 2 \sqrt{d - 1}, 2 \sqrt{d - 1}]$ .

Theorem 4.20 (Bilu, Linial). Can find signings $S$ with eigenvalues $λ$ satisfying $| λ | = O (\sqrt{d {(\log d)}^{3}})$ .

Theorem 4.21 (Marcusm, Spielman, Srivastava). Assuming that:

$G$ is a $d$ -regular graph

Then there exists a signing with eigenvalues

λ

with

λ \leq 2 \sqrt{d - 1}

Theorem 4.21 implies Theorem 4.15.

Start with $K_{d, d}$ .
Keep applying Theorem 4.21 to find signing.
Build lift with that signing.
2-lift of bipartite graph is bipartite.
Spectrum of adjacency matrix of bipartite graph is symmetric around $0$ . □

Notation. For $π \in Sym (X)$ , let $| π |$ be the number of inversions.

Theorem 4.21: $S \sim Unif ({\pm 1}^{E (G)})$ .

\begin{array}{l} 𝔼_{S} \det (x I - S) & = 𝔼_{S} (\sum_{π \in Sym (X)} {(- 1)}^{| π |} \prod_{y \in V} (x I - S) (y, π (y))) \\ = \sum_{k = 0}^{n} x^{n - k} {(- 1)}^{k} \sum_{\begin{array}{c} T \subseteq V \\ | T | = k \end{array}} \sum_{π \in Sym (T)} 𝔼_{S} ({(- 1)}^{| π |} \prod_{y \in T} (x I - S) (y, π (y))) \end{array}

For $x y \in E$ : $𝔼 S {(x, y)}^{2 k + 1} = 0$ , $𝔼 S {(x, y)}^{2 k} = 1$ .

\begin{array}{l} = \sum_{\begin{array}{c} k = 0 \\ k even \end{array}}^{n} x^{n - k} {(- 1)}^{k} \sum_{\begin{array}{c} M matching \\ of size \leq \frac{k}{2} \end{array}} {(- 1)}^{k ∕ 2} \dots \\ = \sum_{k \geq 0} x^{n - 2 k} {(- 1)}^{k} M_{k} (G) \\ = μ_{G} (x) \end{array}

where

M_{k} (G)

is the number of matchings of size

k

G

$μ_{G} (x)$ is the matching polynomial of $G$ .

Heilman-Lieb-Godsil:

$μ_{G} (x)$ is real rooted for all $G$ .
If $G$ has degree $\leq d$ , then $μ_{G} (x)$ has roots in $[- 2 \sqrt{d - 1}, 2 \sqrt{d - 1}]$ .

Last time, when working on $\det (x I - A_{s})$ , we showed:

Theorem 4.22 (Godsil-Gutman, 80s).

𝔼_{S \sim {\pm 1}} \det (x I - A_{s}) = μ_{G} (x),

where

μ_{G} (x) = \sum_{k \geq 0} x^{n - 2 k} {(- 1)}^{k} m_{k} (G),

where $m_{k} (G)$ is the number of matchings in $G$ with $k$ edges.

Fact: $μ_{G} (x)$ is real rooted.

Theorem 4.23 (Heilman-Lieb, 72). Assuming that:

$G$ is $d$ -regular

Then

maxroot μ_{G} (x) \leq 2 \sqrt{d - 1} .

If only we could say that $maxroot 𝔼_{S} \det (x I - A_{s})$ is an average of $maxroot \det (x I - A_{h})$ , $h \in {\pm 1}^{E}$ . Hopelessly false:

Definition 4.24 (Interlacing). Let $f$ be a real rooted polynomial of degree $n$ with roots $α_{1}, \dots, α_{n}$ and $g$ a real rooted polynomial of degree $n - 1$ with roots $β_{1}, \dots, β_{n - 1}$ . We say $g$ interlaces $f$ if

α_{1} \leq β_{1} \leq α_{2} \leq \dots \leq β_{n - 2} \leq α_{n - 1} \leq β_{n - 1} \leq α_{n} .

Example. If $f$ is real rooted, then so is $f^{'}$ , and also $f^{'}$ interlaces $f$ .

Definition 4.25 (Common interlacement). We say that real rooted polynomials $f$ , $g$ of degree $n$ have a common interlacement if there is a polynomial $h$ of degree $n + 1$ such that $f$ and $g$ both interlace $h$ . In other words, if the roots of $f$ and $g$ are $α_{1} \leq \dots α_{n}$ and $β_{1} \leq \dots \leq β_{n}$ respectively, then they have a common interlacement if and only if there are some $γ_{0} \leq \dots \leq γ_{n}$ such that

γ_{0} \leq α_{1}, β_{1} \leq γ_{1} \leq α_{2}, β_{2} \leq γ_{2} \leq \dots \leq γ_{n - 1} \leq α_{n}, β_{n} \leq γ_{n} .

Theorem 4.26 (Fell 80). Assuming that:

$f$ , $g$ are real rooted
both degree $n$ , monic

Then

f

and

g

have a common interlacing if and only if every convex combination of

f

and

g

are real rooted.

Proof. Assume $f$ and $g$ without repeated or common roots (general case requires more work and details checking).

$\Leftarrow$ Let $h_{t} (x) = t f (x) + (t - 1) g (x)$ for $t \in (0, 1)$ . We know these are real rooted, and waht to show that $f$ , $g$ have a common interlacement. Let $λ_{i} (t)$ be the $i$ -th root of $h_{t} (x)$ . $λ_{i} (t)$ includes $(λ_{i} (0), λ_{i} (1)) \subseteq ℝ$ .
Claim: $(λ_{I} (0), λ_{I} (1))$ are disjoint.

Suppose not. Let $λ_{k}$ be a root of $f$ and $λ_{k} \in (λ_{I} (0), λ_{I} (1))$ . So there exists $t \in (0, 1)$ such that $λ_{I} (t) = λ_{k}$ .

$h_{t} (λ_{k}) = 0 = t f (λ_{k}) + (1 - t) g (λ_{k}),$

so $g (λ_{k}) = 0$ , contradiction as we assumed no common roots.
$\Rightarrow$

The dots represent the roots of the polynomial that interlaces them. By monicness, we get the blue and green $+$ s and $-$ s. Then get the orange ones, and use intermediate value theorem. □

Corollary 4.27. Assuming that:

$f$ , $g$ are real rooted of degree $n$
have a common interlacing

Then for all

t \in [0, 1]

\min {maxroot (f), maxroot (g)} \leq maxroot (t f (x) + (1 - t) g (x)) .

Approach to Theorem 4.21:

$f (x) = 𝔼_{S \in {\pm 1}^{E}} \det (x I - A_{s})$ , $| E | = m$ . For $h_{1}, \dots, h_{k} \in {\pm 1} = {+, -}$ , then

f_{h_{1}, \dots, h_{k}} (x) = 𝔼_{s_{k + 1}, \dots, s_{m} \in {\pm 1}} (\det (x I - A_{s}) | s_{1} = h_{1}, \dots, s_{k} = h_{k}) .

“Method of interlacing families of polynomials”

Theorem 4.28 (Marcus, Spielman, Srivastava (real rooted)). For every $ρ_{1}, \dots, ρ_{m} \in [- 1, 1]$ the following polynomial is real rooted

χ_{ρ_{1}, \dots, ρ_{m}} (x) = \sum_{S \in {\pm 1}^{m}} \det (x I - A_{s}) \prod_{J : s_{J} = 1} (\frac{1 + ρ_{J}}{2}) \prod_{J : S_{J} = - 1} (\frac{1 - ρ_{J}}{2}) .

Theorem 4.28 implies Theorem 4.21:

f_{h_{1}, \dots, h_{k}} (x) = χ_{h_{1}, \dots, h_{k}, 0, 0, \dots, 0} (x) .

μ_{G} (x) = χ_{0, \dots, 0} (x) .

t f_{h_{1}, \dots, h_{k}, 1} (x) + (1 - t) f_{h_{1}, \dots, h_{k}, - 1} (x) = χ_{h_{1}, \dots, h_{k}, 2 t - 1, 0, \dots, 0} (x) .

Theorem 4.29 (Marcus, Spielman, Srivastava (matrix)). Assuming that:

$r_{1}, \dots, r_{m} \in ℝ^{n}$ are independent random vectors, whose support has $\leq 2$ points

Then

𝔼 \det (x I - \sum_{j = 1}^{m} r_{j} r_{j}^{⊤})

is real rooted.

Theorem 4.29 implies Theorem 4.28:

$χ_{ρ_{1}, \dots, ρ_{m}} (x)$ is

𝔼 \det (x I - A_{s}) .

$𝔼 \det (x I - A_{s})$ is real rooted if and only if $𝔼 \det ((x + d) I - A_{s})$ is real rooted. This equals

𝔼 \det (x I + (d I - A_{s})) .

Note

d I - A_{S} = \sum_{x \sim y} (e_{x} + S (x, y) e_{y}) {(e_{x} + S (x, y) e_{y})}^{⊤} .

Done.

Definition 4.30 (Real stable). A polynomial $p (z_{1}, \dots, z_{n}) \in ℝ [z_{1}, \dots, z_{n}]$ is real stable if $p (z_{1}, \dots, z_{n}) \neq 0$ for all $(z_{1}, \dots, z_{n}) \in H^{n}$ , $H = {z \in ℂ | Im z > 0}$ .

Notice that for a single variable, $p (z)$ is real stable if and only if real rooted.

Example. $1 - z_{1} z_{2}$ .

Proposition 4.31 (Stable iff real rooted). $p (z_{1}, \dots, z_{n})$ is real stable if and only if for all $ℝ_{\geq 0}^{n}$ , $b \in ℝ^{n}$ , the polynomial $t \mapsto p (a t + b)$ is real rooted.

Proof.

$\Rightarrow$ If $p$ not stable, then there exists $z_{0}, \dots, z_{n} \in H$ with $p (z_{1}, \dots, z_{n}) = 0$ , $z_{j} = b_{j} + i a_{j}$ , $a_{j} > 0$ . Then $p (a i + b) = 0$ , $t = i$ .
$\Leftarrow$ Suppose $\exists a \in ℝ_{\geq 0}^{n}$ , $b \in ℝ^{n}$ , $t \in ℂ ∖ ℝ$ with $p (a t + b) = 0$ . Assume $Im t > 0$ . $z_{j} + a_{j} t + b_{j} \in H$ . $p (z_{1}, \dots, z_{n}) = p (a t + b) = 0$ .

□

Proposition 4.32 (Stability of real stable). Assuming that:

$p (z_{1}, \dots, z_{n})$ is real stable

Then the following are also:

$p (z_{σ (1)}, \dots, z_{σ (n)})$ , $σ \in S_{n}$ .
$p (a z_{1}, z_{2}, \dots, z_{n})$ , $a \in ℝ_{\geq 0}$ .
$p (z_{2}, z_{2}, z_{3}, \dots, z_{n})$ .
$p (c, z_{2}, \dots, z_{n})$ , $c \in H \cup ℝ$ .
$z_{1}^{d_{1}} p (- \frac{1}{z_{1}}, z_{2}, \dots, z_{n})$ .
$\partial_{z_{1}} p (z_{1}, \dots, z_{n})$ .
$MAP (p (z_{1}, \dots, z_{n}))$ . $MAP (z_{1} z_{2} + z_{2} z_{3}^{2} + 2 z_{1} z_{4} + z_{2} z_{3}^{2}) = z_{1} z_{2} + 2 z_{1} z_{4}$ .
If $p, q$ are real stable, then so is $p q$ .

Proposition 4.33 (Mother of all stable polynomials). Assuming that:

$B \in ℝ^{d \times d}$ symmetric matrix
$A_{1}, \dots, A_{m} \in ℝ^{d \times d}$ positive semi definite

Then

\det (B + z_{1} A_{1} + \dots + z_{n} A_{n})

is real stable.

Proof. Let $a \in ℝ_{\geq 0}^{n}$ , $b \in ℝ^{n}$ . Assume positive definite instead of positive semi definite.

\begin{array}{l} \det (B + \sum_{j = 1}^{n} (a_{j} t + b_{j}) A_{j}) = \det (\underset{= : A}{\underset{⏟}{(\sum_{j = 1}^{n} a_{j} A_{j})}} t + \underset{= : C}{\underset{⏟}{(\sum_{j = 1}^{n} b_{j} A_{j} + B)}}) \end{array}

$A$ is positive definite, and $C$ is symmetric. So

\begin{array}{l} = \det (A t + C) \\ = \det (A^{\frac{1}{2}} (t I + A^{- \frac{1}{2}} C A^{- \frac{1}{2}}) A^{\frac{1}{2}}) \\ = \det A \det (t I + A^{- \frac{1}{2}} C A^{- \frac{1}{2}}) \end{array}

The roots are eigenvalues of a real symmetric matrix, hence real. □

Proof of Theorem 4.29. Say $r_{j}$ equals $r_{j}^{+}$ with probability $p_{j}^{+}$ , and equals $r_{j}^{-}$ with probability $p_{j}^{-}$ . We will use Cauchy Binet:

\det (A B) = \sum_{\begin{array}{c}  \end{array}} \det (A_{S \times [n]}) \det (B_{[n] \times C}) T O D O

\begin{array}{l} p (z_{1}, \dots, z_{n}) & = 𝔼 \det (\sum_{j = 1}^{n} z_{j} r_{j} r_{j}^{⊤}) \\ = 𝔼 \sum_{\begin{array}{c} S \subseteq [m] \\ | S | = n \end{array}} \det (\sum_{j \in S} z_{j} r_{j} r_{j}^{⊤}) \\ = 𝔼 \sum_{\begin{array}{c} S \subseteq [m] \\ | S | = n \end{array}} (\prod_{j \in S} z_{j}) \det (\sum_{j \in S} r_{j} r_{j}^{⊤}) \end{array}

\det (𝔼 \sum_{j = 1}^{n} z_{j} r_{j} r_{j}^{⊤}) = \det (\sum_{j = 1}^{n} z_{j} 𝔼 r_{j} r_{j}^{⊤})

is real stable since $𝔼 r_{j} r_{j}^{⊤} \geq 0$ is a covariance matrix.

\begin{array}{l} = \det (\sum_{j = 1}^{m} z_{j} (p_{j}^{+} r_{j}^{+} {(r_{j}^{+})}^{⊤} + p_{j}^{-} r_{j}^{-} {(r_{j}^{-})}^{⊤})) \\ = \sum_{\begin{array}{c} S \subseteq [m] \\ | S | = n \end{array}} (\prod_{j \in S} z_{j}) \sum_{n \in {\pm 1}^{S}} \det (p_{j}^{h (j)} r_{j}^{h (j)} {(r_{j}^{h (j)})}^{⊤}) + “terms with squares” \end{array}

So the earlier thing is real stable. So

𝔼 \det (\sum_{j = 1}^{m} z_{j} r_{j} r_{j}^{⊤})

is real stable. So

𝔼 \det (\sum_{j = 1}^{m} z_{j} r_{j} r_{j}^{⊤} + \sum_{j = 1}^{m} x_{j} e_{j} e_{j}^{⊤})

is real stable. Take $z_{j} = - 1$ , $x_{j} = x$ . Then

𝔼 \det (x I - \sum_{j = 1}^{m} r_{j} r_{j}^{⊤})

is real stable. □

Theorem 4.34 (Godsil). Assuming that:

$G$ is $d$ -regular
$λ_{1} \leq \dots \leq λ_{n}$ are the roots of $μ_{G} (x)$

Then

\sum_{k = 1}^{n} λ_{k}^{l} = \sum_{a} W_{a}^{l} (G),

where $W_{a}^{l} (G)$ is the number of closed walks of length $l$ from $a$ in the path tree $T_{a} (G)$ of $G$ .

Definition 4.35 (Path tree). Example: $T_{a} (G)$

Proof of ?? implies Theorem 4.23. $W_{a}^{l} (G) \leq W_{a}^{l} (\prod_{d}) \leq {(2 \sqrt{d - 1} + o_{l} (1))}^{l}$ .

$λ_{n}^{l} \leq \sum λ_{k}^{l} = \sum_{a} W_{a}^{l} (G) \leq n {(2 \sqrt{d - 1} + o_{l} (1))}^{l}$ .

$λ_{n} \leq n^{\frac{1}{l}} (2 \sqrt{d - 1} + o_{l} (1))$ .

Take $l \to \infty$ . □

Proof of ??. $μ_{G}^{'} (x) = \sum_{a} μ_{G - a} (x)$ Hence

\begin{array}{l} \sum_{a} \sum_{k \geq 0} x^{n - 1 - 2 k} {(- 1)}^{k} m_{k} (G - a) & = \sum_{k \geq 0} (n - 2 k) x^{n - 1 - 2 k} {(- 1)}^{k} m_{k} (G) \\ = μ_{G}^{'} (x) \end{array}

\begin{array}{l} μ_{G} (x) & = x μ_{G - a} (x) - \sum_{b \sim a} μ_{G - a - b} (x) \\ m_{k} (G) & = m_{k} (G - a) + \sum_{b \sim a} m_{k - 1} (G - a - b) \\ x^{n - 2 k} {(- 1)}^{k} m_{k} (G) & = x \cdot x^{n - 1 - 2 k} {(- 1)}^{k} m_{k} (G - a) - \sum_{b \sim a} x^{n - 2 - 2 (k - 1)} {(- 1)}^{k - 1} m_{k - 1} (G - a - b) \\ \sum_{a} \frac{μ_{G - a} (x)}{μ_{G} (x)} & = \frac{μ_{G}^{'} (x)}{μ_{G} (x)} \\ = \sum_{j = 1}^{n} \frac{1}{x - λ_{j}} \\ = \frac{1}{x} \sum_{j = 1}^{n} \frac{1}{1 - \frac{λ_{j}}{x}} \\ = \frac{1}{x} \sum_{j = 1}^{n} \sum_{l \geq 0} \frac{λ_{j}^{l}}{x^{l}} \\ = \frac{1}{x} \sum_{l \geq 0} \frac{\sum_{j} λ_{j}^{l}}{x^{l}} \end{array}

Claim:

\frac{μ_{G - a} (x)}{μ_{G} (x)} = \frac{1}{x} \sum_{l \geq 0} \frac{W_{a}^{l} (G)}{x^{l}}

\begin{array}{l} \frac{μ_{G - a} (x)}{μ_{G} (x)} & = \frac{μ_{G - a} (x)}{x μ_{G - a} (x) - \sum_{b \sim a} μ_{G - a - b} (x)} \\ = \frac{1}{x} \frac{1}{1 - \frac{1}{x} \sum_{b \sim a} \frac{μ_{G - a - b} (x)}{μ_{G - a} (x)}} \\ = \frac{1}{x} \cdot \sum_{k \geq 0} {(\frac{1}{x} \sum_{b \sim a} \frac{μ_{G - a - b} (x)}{μ_{G - a} (x)})}^{k} \\ = \frac{1}{x} \sum_{k \geq 0} \frac{1}{x^{k}} {(\sum_{b \sim a} \frac{1}{x} \sum_{l \geq 0} \frac{W_{b}^{l} (G - a)}{x^{l}})}^{k} \\ = \frac{1}{x} \sum_{k \geq 0} \frac{1}{x^{2 k}} (\sum_{b_{1} \sim a} \sum_{l_{1} \geq 0} \frac{W_{G}^{l_{1}} (G - a)}{x^{l_{1}}}) \dots (\sum_{b_{k} \sim a} \sum_{l_{k} \geq 0} \frac{W_{b_{k}}^{l_{k}} (G - a)}{x^{l_{k}}}) \\ = \frac{1}{x} \sum_{l \geq 0} \frac{W_{a}^{l} (G)}{x^{l}} \end{array}

Why? A tree-like walk in $W_{a}^{l} (G)$ that visits $a$ exactly $k$ times is determined by:

A sequence $b_{1}, \dots, b_{k}$ of neighbours of $a$ .
A sequence $γ_{1}, \dots, γ_{k}$ of walks in $T_{b_{i}}^{l_{i}} (G - a)$ where $2 k + l_{1} + \dots + l_{k} = l$ .

□