Expander Graph Learning Notes

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Introduction to Expander Graphs

Measures of Expansion

First, there are two combinatorial definitions of expansion.

Definition (Edge Expansion): A $D$-regular graph $G$ is a $(K,\epsilon)$ edge expander if for all sets $S$ of at most $K$ vertices, the cut size $e(S,\bar{S})$ is at least $\epsilon |S|D$.

In addition, we define $h(G)$ by:

$h(G):=\min_{S\subset V\text{ and }|S|\le |V|/2} \dfrac{e(S,\bar{S})}{d|S|}$

Definition (Vertex Expansion): A graph $G$ is a $(K,A)$ vertex expander if for all sets $S$ of at most $K$ vertices, the neighborhood $N(S) := \{u\mid ∃v ∈ S\text{ s.t. }(u,v) ∈ E\}$ is of size at least $A · |S|$.

And then, there is another definition of expansion.

Definition (Spectral Expansion): For $\gamma \in [0,1]$, we say that a regular graph $G$ has spectral expansion $\gamma$ if $\gamma(G):=1-\lambda(G)\ge \gamma$, where $\lambda(G)$ is the second eigenvalue of the normalized adjacency matrix $M(G)$.

Note that by Rayleigh theorem, we have:

$\lambda(G)=\max_{\pi\ne \bm 0}\dfrac{\|\pi M-\bm{1}\|}{\|\pi -\bm{1}\|}=\max_{x \bot \bm{1}}\dfrac{\|x M\|}{\|x\|}$

Some Relations between Different Definitions

Expander Mixing Lemma

We will prove a famous result known as the expander mixing lemma, which gives a relation between a graph’s spectral expansion and a certain regularity or spreadness condition of its edges that is a slightly more general statement than edge-expansion itself.

Theorem (Expander Mixing Lemma): Let $G$ be a $D$-regular, $N$ vertex graph with spectral expansion $1-\lambda$. Then for all sets of vertices $S,T$, we have:

$\left | \dfrac{e(S,T)}{ND}-\mu(S)\mu(T) \right |\le \lambda\sqrt{\mu(S)(1-\mu(S))\mu(T)(1-\mu(T))}$

$\le \lambda\sqrt{\mu(S)\mu(T)}\le \lambda$

where $\mu(H)\,(H\subset V(G))$ denote the denstity of $H$, $|H|/N$.

Proof: Let $\bm{1}_S,\bm{1}_T$ be the characteristic row vector of $S$ and $T$, i.e. $(\bm{1}_S)_i=[i\in S]$.

By using orthogonal decompostion, we can write $\bm{1}_S$ as: $\bm{1}_S=\dfrac{\langle \bm{1}_S,\bm{1}\rangle}{\langle \bm{1},\bm{1}\rangle}\bm{1}+\bm{1}_S^\bot=\bm{1}\sum_i(\bm{1}_S)_i+\bm{1}_S^\bot=\mu(S)N\bm{1}+\bm{1}_S^\bot$. Similarly, $\bm{1}_T=\mu(T)N+\bm{1}_T^\bot$.

Then:

$\dfrac{e(S,T)}{ND}=\dfrac 1N (\mu(S)N\bm{1}+\bm{1}_S^\bot)M(\mu(T)N\bm{1}+\bm{1}_T^\bot)^T$

Notice that $\bm{1}M=\bm{1},Mu^T=\bm{1}^T,\bm{1}\bm{1}^T=1/N$. Thus:

$\left| \dfrac{e(S,T)}{ND}-\mu(S)\mu(T) \right|=\left|\dfrac{\bm{1}_S^\bot M(\bm{1}_T^\bot)^T}N\right|\le \dfrac{\|\bm{1}_S^\bot M\|\|\bm{1}_T^\bot\|}N\le \dfrac{\lambda\|\bm{1}_S^\bot\|\|\bm{1}_T^\bot\|}N$

Notice that $\mu(S)N=\|\bm{1}_S\|^2=\|\mu(S)N\bm{1}\|^2+\|\bm{1}_S^\bot\|^2=\mu^2(S)N+\|\bm{1}_S^\bot\|^2$. Thus we have: $\|\bm{1}_S^\bot\|=\sqrt{\mu(S)(1-\mu(S))}$. Similarly, $\|\bm{1}_T^\bot\|=\sqrt{\mu(T)(1-\mu(T))}$.

The above then implies:

$\left | \dfrac{e(S,T)}{ND}-\mu(S)\mu(T) \right |\le \lambda\sqrt{\mu(S)(1-\mu(S))\mu(T)(1-\mu(T))}$

$\le \lambda\sqrt{\mu(S)\mu(T)}\le \lambda$

as desired. $\Box$

Expander mixing lemma also has its converse. We present here without proving it.

Theorem (Converse to Expander Mixing Lemma): Let $G$ be a $D$-regular, $N$-vertex graph. Suppose that for all pairs of disjoint vertex sets $S,T$, we have $|e(S,T)/(ND) − \mu(S)\mu(T)| ≤θ\sqrt{\mu(S)\mu(T)}$ for some $θ ∈ [0,1]$. Then $λ(G) = O(θ \log(1/θ))$.

Cheeger Inequaltiy

Theorem (Cheeger Inequality): Let $G$ be a $D$-regular graph, then:

$\dfrac{1 − λ(G)}2≤ h(G) ≤\sqrt{2(1 − λ(G))}$

Proof: （鸽子一会）$\Box$

Random Walks on Expanders

Due to the good struction of expanders, we can use the random walk on expanders to reduce the randomness needed by random algorithms.

Hitting Property of Expander Walks: If $G$ is a regular graph with spectral expansion $1 − λ$, then for any $B \subset V(G)$ of density $\mu$, the probability that a random walk $(V_1,\ldots,V_t)$ of $t − 1$ steps in $G$ starting in a uniformly random vertex $V_1$ always remains in $B$ is

$\Pr\left[\bigwedge_{i=1}^t V_i\in B \right]\le (\mu+\lambda(1-\mu))^t$

Proof: Firstly, we prove a lemma:

Lemma: The probability that the random walk stays entirely within $B$ is precisely $\|\bm 1P(MP)^{t−1}\|_1$, where $P$ is defined as follow:

$P_{ij}=\begin{cases} [i\in B] & i=j \\ 0 & i\ne j \end{cases}$

Proof of Lemma: We can easily prove this lemma by induction on $t$. $\blacksquare$

And there becomes anther lemma:

Lemma: $\|PMP\|\le \mu+\lambda(1-\mu)$, where $\|\cdot \|$ denotes the spectral norm of matrices.

Proof of Lemma: We decompose $M$ into two parts:

$M=\gamma J+\lambda E$

Then we have:

$\|PMP\|=\|P(\gamma J+\lambda E)P\| \\ \le \gamma \|PJP\|+\lambda \|PEP\|\le \gamma \|PJP\|+\lambda$

Noet that the last inequality uses the fact that $\|E\|\le 1$.

For all $x\in \mathbb R^N$, let $y$ be $xP$, then $xPJP=yJP=\left(\sum_i y_i \right)\bm 1 P$.

Since:

$\|xPJP\|_2\le \left|\sum_i y_i \right|\|\bm 1P\|_2\le \sqrt{\mu N}\|y\|_2\sqrt{\dfrac\mu N}\le \mu \|x\|$

Noet that the last inequality uses the fact that $\|y\|_2\le \|x\|_2$.

Thus:

$\|PMP\|\le \gamma \mu+\lambda=\mu+\lambda(1-\mu)$

as desired. $\blacksquare$

By combining two above lemmas, we can get that:

$\|\bm 1 P(MP)^{t-1}\|_1=\|\bm 1 P(PMP)^{t-1} \|_1\le \sqrt{\mu N}\|\bm 1 P(PMP)^{t-1}\|_2 \\ \le \sqrt{\mu N}\|\bm 1P\|_2 \|PMP\|^{t-1}\le \sqrt{\mu N}\sqrt{\dfrac{\mu}N}(\mu +\lambda(1-\mu))^{t-1}\le (\mu+\lambda(1-\mu))^t$

as desired. $\Box$

To reduce the randomness of a $\textbf{RP}$ algorithm $A$ which uses $m$ random bits, the general approach is to consider an expander graph with vertex set ${0,1}^m, where each vertex is associated with a setting of the random bits. We will choose a uniformly random vertex $V_1$ and then do a random walk of length $t − 1$, visiting additional vertices $V_2,\ldots,V_t$. This requires $m$ random bits for the initial choice, and
$\log D$ for each of the $t − 1$ steps. For every vertex $V_i$ on the random walk, we will run the algorithm with $V_i$ as the setting of the random coins.

Then by the theorem above, in order to reduce the error probability to $2^{-k}$, the length of the random walk should be $\Theta(k)$. Thus, the number of random bits is $m+O(k)$.

The success of the error-reduction procedure for two-sided error algorithms is obtained by the following theorem.

Chernoff Bound for Expander Walk: Let $G$ be a regular graph with $N$ vertices and spectral expansion $1 − λ$, and let $B\in [N]$ be a subset of vertices. Consider a random walk $V_1,\ldots,V_t$ in $G$ from a uniform start vertex $V_1$. Then for any $\epsilon > 0$

$\Pr\left[\left|\dfrac 1t \sum_{i=1}^t [V_i\in B] -\mu(B) \right| \ge \epsilon \right]\le 2\text{e}^{-(1-\lambda)\epsilon^2t/4}$

Proof:

Corollary: If a language $L$ has a $\textbf{BPP}$ algorithm with error probability at most $1/3$ that uses $m(n)$ random bits on inputs of length $n$, then for every polynomial $k(n)$, $L$ has a BPP algorithm with error probability at most $2^{−k(n)}$ that uses $m(n) + O(k(n))$ random bits.

Optimal Expanders

How good can the expansion of a graph be?

For vertex expansion, the following theorem shows its limitation.

Theorem (Limits on Vertex Expansion)：

(1) Show that if a $D$-regular graph $G$ is a $(K,A)$ expander, then $T_D$ is a $(K,A)$ expander, where $T_D$ is the infinite $D$-regular tree.

(2) Show that for every $D \in \mathbb N$, there are infinitely many $K \in \mathbb N$ such that $T_D$ is not a $(K,D − 1+2/K)$ expander.

(3) Deduce that for constant $D \in \mathbb N$ and $α > 0$, if a $D$-regular, $N$-vertex graph $G$ is an $(αN,A)$ vertex expander, then $A ≤D − 1 + o(1)$, where the $o(1)$ term vanishes as $N \to \infty$ (and $D, α$ are held constant).

For spectral expansion, the result is known as Alon–Boppana Bound.

Theorem (Alon–Boppana Bound): Let $G$ be a $D$-regular graph, then:

$\lambda(G)\ge \dfrac{2\sqrt{D-1}}D-o(1)$

where the $o(1)$ term vanishes as $N\to \infty$.

Proof: For a graph $H$, let $p_l(H)$ denote the probability that if we choose a random vertex $v$ in $H$ and do a random walk of length $2l$, we end back at vertex $v$. And let $T_D$ be the infinite $D$-regular tree.

Obviously, we have: $p_l(G)\ge p_l(T_D)$.

A random walk of length $2l$ which end back at starting vertex can be seen as a properly parenthesized string of length $2l$ with at least $D-1$ types of parentheses.

Thus: $p_l(T_D)\ge C_l(D-1)^l/D^{2l}$, where $C_l$ is the $l$-th Catalan number.

In addition, we have: $\text{tr}(M^{2l})=1+\lambda_2^{2l}+\cdots+\lambda_n^{2l}\le 1+(N-1)\lambda^{2l}(G)$ and: $p_l(G)=\sum_{v\in G}p_{l,v}(G)/N=\text{tr}(M^{2l})/N$.

Thus we have: $Np_l(G)\le 1+(N-1)\lambda^{2l}(G)$.

Notice that $C_l=\dbinom {2l}l/(l+1)$. Then using the inequality proved above, we have:

$1+(N-1)\lambda^{2l}(G)\ge Np_l(G)\ge NC_l(D-1)^l/D^{2l}=N\dfrac{\binom{2l}l(D-1)^l}{(l+1)D^{2l}}$

Thus:

$\lambda(G)\ge \sqrt[2l]{\dfrac{N(2l)!}{(l+1)(l!)^2}}\cdot \dfrac{\sqrt{D-1}}D$

Let $l=N$, then use Stirling’s Approximation, we have:

$\lambda(G)\ge \dfrac{\sqrt{D-1}}D\cdot \sqrt[2N]{\dfrac{\sqrt{2\pi \cdot 2N}(2N/\text{e})^{2N}}{(\sqrt{2\pi N}(N/\text{e})^{N})^2}}\cdot \sqrt[2N]{\dfrac N{N+1}}$

$=\dfrac{2\sqrt{D-1}}D-o(1)\ (N\to \infty)$

as desired. $\Box$

The optimal spectral expander is called as the Ramanujan graph.

Definition (Ramanujan Graphs): A $d$-regular graph $G$ is called as a Ramnujan graph if $\lambda(G)\le \dfrac{2\sqrt{D-1}}D+o(1)$.

We will discuss some explicit constructions of Ramnujan graphs in the next section.

Explicit Constructions

A random graph will be a good expander but we will not choose it as an expander. Some reasons we don’t choose it:

• Don’t want to tolerate the error probability that the graph isn’t an expander, and checking it is $\text{NP-Hard}$ problem.
• Defeat the purpose that we want to reduce randomness.
• Require exponentially large expander graphs, and thus we can’t even write down a randomly chosen expander.

Mildly Explicit: Construct a complete representation of the graph in time an $\text{poly}(N)$.

Fully Explicit: Given a mode $u\in [N]$ and $i\in [D]$, where $D$ is the degree of the expander, compute the $i$th nerghbor of $u$ in time $\text{poly}(\log N)$. (more efficiently)

Goal: Devise a fully explicit construction of an infinite family $\{G_i \}$ of $D$-regular graphs with spectral expansion at least $\gamma$, where $D$ and $\gamma >0$ are constants independent of $i$.

Algebraic Constructions

Discrete torus expanders, $p$-cycle with inverse chords.

Ramanujan Graphs: $G = (V,E)$ is a graph with vertex set $V = \mathbb F_q \cup \{\infty\}$, the finite field of prime order $q$ s.t. $q \equiv 1 \pmod 4$ plus one extra node representing infinity. The edges in this graph connect each node $z$ with all $z'$ of the form:

$z' = \dfrac{(a_0 + ia_1)z + (a_2 + ia_3)}{(−a_2 + ia_3)z + (a_0 − ia_1)}$

for $a_0, a_1, a_2, a_3 ∈ \mathbb Z$ such that $a^2_0 + a^2_1 + a^2_2 + a^2_3 = p$, $a_0$ is odd and positive, and $a_1, a_2, a_3$ are even, for some fixed prime $p \ne q$ such that $p \equiv 1 \pmod 4$, $q$ is a square modulo $p$, and $i \in \mathbb F_q$ such that $i^2 = −1 \pmod q$.

It’s an optimal spectral expander. (?, omit the proof)

Graph Operations

Definition: An $(N,D,\gamma)$-graph is a $D$-regular graph on $N$ vertices with spectral expansion $\gamma$.

Squaring

Definition (Squaring of Graphs): If $G = (V,E)$ is a $D$-regular graph, then $G^2 = (V,E')$ is a $D^2$-regular graph on the same vertex set, where the $(i, j)$th neighbor of a vertex $x$ is the $j$th neighbor of the $i$th neighbor of $x$.

Lemma: If $G$ is a $(N,D,1 − \lambda)$-graph, then $G^2$ is a $(N,D^2,1 − λ^2)$-graph.

Proof: Let $M$ be the random walk matrix for $G$, and then $M^2$ is the random walk matrix for $G^2$. Thus: $\forall x\bot \bm{1}, \|xM^2 \|\le \lambda \|xM \|\le \lambda^2 \| x\|$. $\Box$

Tensor

Definition (Tensor Product of Graphs): Let $G_1 = (V_1,E_1)$ be $D_1$-regular and $G_2 = (V_2,E_2)$ be $D_2$-regular. Then their tensor product is the $D_1D_2$-regular graph $G_1 \otimes G_2 = (V_1 × V_2,E)$, where the $(i_1, i_2)$th neighbor of a vertex $(x_1,x_2)$ is $(y_1,y_2)$, where $y_b$ is the $i_b$th neighbor of $x_b$ in $G_b$.

A Few Comments on the Tensor of Matrix and Vector:

• $(x ⊗ y)(A ⊗ B)=(xA) ⊗ (yB)$.
• $M_1 ⊗ M_2 = (I_{N_1} ⊗ M_2)(M_1 ⊗ I_{N_2} )=(M_1 ⊗ I_{N_2} )(I_{N_1} ⊗ M_2)$.

Lemma: If $G_1$ is an $(N_1,D_1, \gamma_1)$-graph and $G_2$ is an $(N_2,D_2, \gamma_2)$- graph, then $G_1 ⊗ G_2$ is an $(N_1N_2,D_1D_2,\min\{γ_1, γ_2\})$-graph.

Proof: Let $M_1,M_2$ be the random walk matrix for $G_1$ and $G_2$, and then $M\triangleq M_1\otimes M_2$ is the random walk matrix for $G_1 \otimes G_2$.

$\forall x(\in \mathbb R^{N_1N_2})\bot \bm{1}_{N_1N_2}$, decompose $x$ as $x = x^{\|} + x^\bot$, where $x^{\|}$ is a multiple of $\bm{1}_{N_2}$ on each cloud of size $N_2$ and $x^\bot$ is orthogonal to $\bm{1}_{N_2}$ on each cloud.

Note that $\langle x^\bot,\bm{1}_{N_1N_2} \rangle=\sum\limits_{S\in\text{each cloud}}\langle x^\bot|_S,\bm{1}_{N_2} \rangle=0$. Thus, $\langle x^\|,\bm{1}_{N_1N_2} \rangle=\langle x,\bm{1}_{N_1N_2} \rangle-\langle x^\bot,\bm{1}_{N_1N_2} \rangle=0$, i.e. $x^\| \bot \bm{1}_{N_1N_2}$. Therefore, if we write $x^\bot$ as $x^\bot=y\otimes \bm{1}_{N_2}$, then $y\bot \bm{1}_{N_1}$.

For the first case, we have: $x^{\|}M = (y ⊗ \bm{1}_{N_2} )(M_1 ⊗ M_2)=(yM_1) ⊗ \bm{1}_{N_2}$. The expansion $G_1$ tells us that $M_1$ shrinks $y$ by a factor of $λ_1$, and thus $\|x^{\|}M\|=\sqrt{N_2}\|yM\|\le \lambda_1 \sqrt{N_2}\|y\| = λ_1 \|x^{\|}\|$.

For another case, we have: $x^\bot M = x^\bot (I_{N_1} ⊗ M_2)(M_1 ⊗ I_{N_2} )$. The expansion of $G_2$ tells us that $M_2$ will shrink $x^\bot$ by a factor of $λ_2$ on each cloud, and thus $I_{N_1} ⊗ M_2$ will shrink $x^\bot$ by the same factor. The subsequent application of $M_1 ⊗ I_{N_2}$ cannot increase the length. Thus, $\|x^\bot M\| ≤ λ_2\|x^\bot\|$.

Finally, we argue that $x^\|M$ and $x^\bot M$ are orthogonal. Note that $x^\|M = (yM_1) ⊗ \bm{1}_{N_2}$ is a multiple of $\bm{1}_{N_2}$ on every cloud. Thus it suffices to argue that $x^\bot$ remains orthogonal to $\bm{1}_{N_2}$ on every cloud after we apply $M$. Applying $I_{N_1} ⊗ M_2$ retains this property and applying $M_1 ⊗ I_{N_2}$ retains this property because it assigns each cloud a linear combination of several other clouds.

The above then implies:

$\|xM\|^2=\|x^\| M\|^2+\|x^\bot M\|^2\le \lambda_1^2\|x^\|\|^2+\lambda_2^2\|x^\bot\|^2\\ \le \max\{\lambda_1,\lambda_2\}^2(\|x^\|\|^2+\|x^\bot\|^2)=\max\{\lambda_1,\lambda_2\}^2\|x\|^2$

as desired. $\Box$

Zig–Zag Product

Definition (Zig–Zag Product): Let $G$ be a $D_1$-regular digraph on $N_1$ vertices, and $H$ a $D_2$-regular digraph on $D_1$ vertices. Then $G Ⓩ H$ is a graph whose vertices are pairs $(u, i) \in [N_1] × [D_1]$. For $a, b ∈ [D_2]$, the $(a, b)$th neighbor of a vertex $(u, i)$ is the vertex $(v,j)$ computed as follows:

(1) Let $i'$ be the $a$th neighbor of $i$ in $H$.

(2) Let $v$ be the $i'$th neighbor of $u$ in $G$, so $e = (u,v)$ is the $i'$th edge leaving $u$. Let $j'$ be such that $e$ is the $j'$th edge entering $v$ in $G$.

(3) Let $j$ be the $b$th neighbor of $j'$ in $H$.

Lemma: If $G$ is a $(N_1,D_1, γ_1)$-graph, and $H$ is a $(D_1,D_2, γ_2)$-graph then $G Ⓩ H$ is a $(N_1D_1,D_2^2, γ = γ_1 · γ_2^2 )$-graph. In particular, if $γ_1 = 1 − λ_1$ and $γ_2 = 1 − λ_2$, then $γ = 1 − λ$ for $λ ≤ λ_1 + 2λ_2$.

Proof: (TODO)

Replacement Product

Definition (Replacement Product): Given a $D_1$-regular graph $G_1$ on $N_1$ vertices and a $D_2$-regular graph $G_2$ on $D_1$ vertices, consider the following graph $G_1 ⓡ G_2$ on vertex set $[N_1] × [D_1]$: vertex $(u, i)$ is connected to $(v,j)$ iff $u = v$ and $(i, j)$ is an edge in $G_2$, or $v$ is the $i’$th neighbor of $u$ in $G_1$ and $u$ is the $j$th neighbor of $v$.

(1) Prove that there is a function $g$ such that if $G_1$ has spectral expansion $γ_1 > 0$ and $G_2$ has spectral expansion $γ_2 > 0$ (and both graphs are undirected), then $G_1 ⓡ G_2$ has spectral expansion $g(γ_1, γ_2,D_2) > 0$.

(2) Show how to convert an explicit construction of constant degree spectral expanders into an explicit construction of degree $3$ spectral expanders.

(3) Without using Theorem 4.14, prove an analogue of Part 1 for edge expansion. That is, there is a function h such that if G1 is an (N1/2,ε1) edge expander and G2 is a (D1/2,ε2) edge expander, then G1 $r G2 is a (N1D1/2,h(ε1,ε2,D2)) edge expander, where h(ε1,ε2,D2) > 0 if ε1,ε2 > 0. (Hint: given any set S of vertices of G1 $r G2, partition S into the clouds that are more than “half-full” and those that are not.)

(4) Prove that the functions $g(γ_1, γ_2,D_2)$ and $h(ε_1,ε_2,D_2)$ must depend on $D_2$, by showing that $G_1 ⓡ G_2$ cannot be a $(N_1D_1/2,ε)$ edge expander if $ε > 1/(D_2 + 1)$ and $N_1 ≥ 2$.

The Expander Construction

Construction of Mildly Explicit Expanders: Let $H$ be a $(D^4,D,7/8)$-graph, and define:

$G_1=H^2\\ G_{t+1}=G_t^2 Ⓩ H$

We can easily prove that for all $t$, $G_t$ is a $(D^{4t},D^2,1/2)$-graph.

To bound the time to compute neighbors in $G_t$, we let $\text{time}(G_t)$ be the time to find the $I$th neighbor of $X$ in $G_t\ (X\in [D^{4t}],I\in [D^2])$.

First, to do zig-zag product, we should caculate $(u,i)$ and $(a,b)$. By properly labeling of vertices and edges, we can caculate them in $\text{poly}(\log N_t)$ time (e.g. vertex $(u,i)$ in $G_t$ can be labelled as $(u-1)D^2+i$, and edge $(a,b)$ in $G_t$ can be labelled as $(a-1)D+b$).

And then, walk on $H$ only takes the constant time, while walk on $G_{t-1}^2$ takes $2\text{time}(G_{t-1})$ time (coefficient $2$ is due to squaring).

Therefore: $\text{time}(G_t)=2\text{time}(G_{t-1})+\text{poly}(\log N_t)=2^t\text{poly}(\log N_t)=N_t^{\Theta(1)}$, where the last equality holds because $N_t = D^{4t}$ for a constant $D$. Thus,
this construction is only mildly explicit.

Construction of Fully Explicit Expanders: Let $H$ be a $(D^8,D,7/8)$-graph, and define:

$G_1 = H^2\\ G_{t+1} = (G_t ⊗ G_t)^2 Ⓩ H$

Obviously, we have: $N_t=N_{t-1}^2D^8$. Thus: $N_t\approx c^{2^t}$.

Therefore: $\text{time}(G_t)=4\text{time}(G_{t-1})+\text{poly}(\log N_t)=4^t\text{poly}(\log N_t)=\text{poly}(\log N_t)$. This construction is fully explicit.

A Better Construction of Fully Explicit Expanders: Let $H$ be a $(D^8,D,7/8)$-graph, and define:

$G_1 = H^2\\ G_{t+1} = (G_{\lfloor t/2\rfloor} ⊗ G_{\lceil t/2\rceil})^2 Ⓩ H$

Now $N_t = D^{8t}$, and $\text{time}(G_t)=O(\text{time}(G_{\lfloor t/2\rfloor})+\text{time}(G_{\lceil t/2\rceil}))+\text{poly}(\log N_t)=\text{poly}(t)$.

However, these constructions do not reach Alon–Boppana Bound, i.e. they are all not the optimal spectral expanders. Therefore here remains an open problem.

Open Problem: Give an explicit “combinatorial” construction of constant-degree expander graphs $G$ with $λ(G) ≤ 2\sqrt{D − 1}/D+o_N(1)$ (or even $λ(G) = O(1/\sqrt D)$), where $D$ is the degree.

Margulis-Gabber-Galil’s Construction

(TODO)

Undirected S-T Connectivity in Deterministic Logspace

Algorithm (Undirected S-T Connectivity in $\text{L}$):

Input: An undirected graph $G$ with $N$ edges and vertices $s$ and $t$.

(1) Let $H$ be a fixed $(D^4,D,3/4)$ graph for some constant $D$.

(2) Reduce $(G,s, t)$ to $(G_0,s_0, t_0)$, where $G_0$ is a $D^2$-regular graph in which every connected component is nonbipartite and $s_0$ and $t_0$ are connected in $G_0$ iff $s$ and $t$ are connected in $G$.

(3) For $k = 1,...,l = O(\log N)$, define:

• Let $G_k = G^2_{k−1} Ⓩ H$.
• Let $s_k$ and $t_k$ be any two vertices in the “clouds” of $G_k$ corresponding to $s_{k−1}$ and $t_{k−1}$, respectively.

(4) Try all paths of length $O(\log N)$ in $G_l$ from $s_l$ and accept if any of them visit $t_l$.

Some Problems

Problem (More Combinatorial Consequences of Spectral Expansion): Let $G$ be a $D$-regular, connected, undirected, nonbipartite graph on $N$ vertices with spectral expansion $γ = 1 − λ$. Prove that:

(1) The independence number $α(G)$ is at most $λN/(1 + λ)$.

(2) The chromatic number $χ(G)$ is at least $(1 + λ)/λ$.

(3) The diameter of $G$ is $O(\log_{1/λ} N)$.

Proof:

(1) Let $S$ be the maximum independent set of $G$, then $e(S,S)$=0.

By Expander Mixing Lemma, we have: $\mu^2(S)\le \lambda \mu(S)(1-\mu(S))\Rightarrow \mu(S)\le \lambda/(1+\lambda)$.

Thus, $α(G)=\mu(S)N$ is at most $λN/(1 + λ)$, as desired.

(2) Let $c:V(G)\to [\chi(G)]$ be the coloring mapping of $G$.

Notice that for every $1\le i\le \chi(G)$, $c^{-1}(i)$ is an independent set of $G$.

Thus: $N=\sum_{i=1}^{\chi(G)}|c^{-1}(i)|\le \chi(G) \cdot \lambda N/(1+\lambda)\Rightarrow \chi(G)\ge (1+\lambda)/\lambda$, as desired.

(3) Let $M$ be the random walk matrix for $G$, and it has eigenvalues $|\lambda_1|\ge |\lambda_2|\ge \ldots \ge |\lambda_n|$, where $\lambda_1=1$ and $|\lambda_i|\le \lambda\,(i>1)$.

By using spectral decomposition, we can write $M$ as:

$M=\sum_{i=1}^N \lambda_i v_iv_i^T$

where $v_1,\ldots,v_n$ denote normalized orthonormal column eigenvectors with eigenvalues $\lambda_1,\ldots,\lambda_n$.

For a positive integer $m$, consider arbitrary entry of matrix $M^m$:

$\begin{aligned} (M^m)_{r,s} & =\sum_{i=1}^N \lambda_i^m (v_iv_i^T)_{r,s} \\ & \ge \dfrac 1N - \left|\sum_{i=2}^N \lambda_i^m (v_i)_r (v_i)_s \right| \\ & \ge \dfrac 1N - \lambda^m\left|\sum_{i=2}^N (v_i)_r (v_i)_s \right| \\ & \ge \dfrac 1N - \lambda^m\sqrt{\sum_{i=2}^N (v_i)_r^2 \sum_{i=2}^N (v_i)_s^2} \\ & = \dfrac 1N - \lambda^m\sqrt{(1-(v_1)_r^2)(1-(v_1)_s^2)} \\ & = \dfrac 1N -\lambda^m(1-1/N) \end{aligned}$

Thus if we have $m>\log_{1/\lambda}(N-1)$, then $\forall 1\le r,s\le N,(M^m)_{r,s}>0$, i.e. $M^m$ has all entries positive.

Therefore the diameter of $G$ is at most $\lfloor \log_{1/\lambda}(N-1)+1 \rfloor$, as desired. $\Box$

Problem (Error Reduction For Free): Show that if a problem has a $\textbf{BPP}$ algorithm with constant error probability, then it has a $\textbf{BPP}$ algorithm with error probability $1/n$ that uses exactly the same
number of random bits.

Proof: Let $A(x;r)$ be the $\textbf{BPP}$ algorithm of this problem, which $r\in \{0,1\}^m$.

Then we can design an expander with $2^m$ vertices, and do a random walk on it. However, this method costs the extra ranom bits.

Notice that if we only want to reduce error probability less than $1/n$, the length of the random walk is only $O(\log n)$. Thus we can directly try all paths of length $O(\log n)$ in polynomial time by using some method such as depth first search. By this way, we only need to randomly choose the starting vertex, which only need $m$ random bits. $\Box$

Reference

[1] Pseudorandomness. Salil P. Vadhan, 2012. From Harvard University, site: https://people.seas.harvard.edu/~salil/pseudorandomness/

[2] Expander Graphs and Their Applications. Shlomo Hoory, Nathan Linial, Avi Wigderson, 2006. From Hebrew University of Jerusalem, site: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

[3] Expander graphs and High-Dimensional Expanders. Shachar Lovett, Max Hopkins. From University of California San Diego, site: https://cseweb.ucsd.edu/classes/sp21/cse291-g/

[4] Computational Complexity: A Modern Approach. Sanjeev Arora, Boaz Barak, 2009.

[5] Chung, F. R. K. (1989). “Diameters and eigenvalues”. Journal of the American Mathematical Society. 2 (2): 187–196. doi:10.1090/S0894-0347-1989-0965008-X. ISSN 0894-0347.