C1: Random Walks on Expander Graphs (1)

November 19, 2024

• Basics before Starting
  • Example 1
  • Example 2
  • Example 3
• Expander Mixing Lemma
  • What is $\lambda_1$, $\alpha_1, \beta_1$?
• Reference

Basics before Starting

Basic skills are of great importance in theory of computer science (by many people).

Given a matrix, how to select a row using matrix languages?

Example 1

Given $M = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} ​​$

If we want to select the second row. Let $\mathbb{1}_s = (0,1,0)$ be the indicator vector.

Then, $(0,1,0) \cdot \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} = (4, 5, 6)$

We successfully do it!

Similarly, if we want to select the second column.

$$M = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} ​​$$

Let $\mathbb{1}_t = (0,1,0)^T$.

Then, $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 2 \\ 5 \\ 8 \end{pmatrix}$

In summary, if we want to select the row, we use

$$\mathbb{1}_s \cdot M$$

if we want to select the column, we use

$$M\cdot \mathbb{1}_t$$

Example 2

Now, consider $M$ to be an adjacency matrix ( 0-1 matrix).

By Example 1, we can easily how to select a set $S$ from $M$.

Let $\mathbb{1}_s$ be the indicator vector of $S$, e.g.,, $\mathbb{1}_s = (0,1,\cdots,1)$

But what does it mean?

$\mathbb{1}_s \times M[:1]$:

if $v_1$ has an incident edges to any node in $S$, then the above result is not zero. It means the number of edges incident from $S$ to $v_1$. So, the multiplication result means the vector of the number of edges from $v_1,v_2,\cdots,v_n$ to $S$

Example 3

Let $E(A, B)$ denote the number of edges from $A$ to $B$. How to denote that using the matrix language.

To solve this problem, we can divide it into two steps.

1. Find the edges from $V$ to $S$.
2. Choose $T$ from $V$.

We use $\mathbb{1}_s \cdot M$ to denote step 1. Then, we times $\mathbb{1}_t^T$ to select $T$ from $V$. In total, we use $\mathbb{1}_s \cdot M \cdot \mathbb{1}_t^T$

Expander Mixing Lemma

$\textbf{Lemma}$. Let $G$ be a $d$-regular graph with $n$ vertices and let $\lambda = \lambda(G) = \max (\lvert \lambda_2\rvert, \lvert \lambda_n \rvert)$. Then, for any $A, B \subseteq V$, we have

$$\left\lvert \lvert E(A, B) \vert - \frac{d\lvert A \rvert \lvert B \rvert}{n} \right\rvert \leq \lambda \sqrt{\lvert A \rvert \lvert B\rvert}$$

What does the expander mixing lemma mean?

$\frac{d\lvert A \rvert \lvert B \rvert}{n}$ means that in a random graph, the number of edges between $A$ and $B$ in expectation.

Therefore, the expander mixing lemma means that the number of edges between $A$ and $B$ in the $d$-regular graph is close to that in a random graph!

$\textbf{Proof}$. The first thing we need to do is that we use the matrix language to denote $E(A,B)$.

$$E(A,B) = \mathbb{1}_a M \mathbb{1}_b^T$$

Since $M$ is an adjacency matrix, it is symmetric, which means that

$M = Q^T\wedge Q$ where $Q$ is an orthogonal matrix.

Then,

$$\wedge =Q M Q^T$$

We have the indicator vectors (or characteristic vectors) as follows.

$$\mathbb{1}_a = \sum_i \alpha_i q_i, \mathbb{1}_b = \sum_j\beta_j q_j^T,$$

where $q_i = \frac{1}{\sqrt{n}}(0,0,0, \cdots, 1, 0,0)$ (the i-th place is 1).

The reason we do not use $(0,0,0, \cdots, 1, 0,0)$ to denote the $\mathbb{1}_a$ is that we will make an orthogonal vector in use.

Therefore, $E(A,B) = \sum_i \alpha_i q_i M \sum_j \beta_j q_j^T,$

Notice that

$$\sum_i q_i M \sum_j q_j^T = \wedge \cdot E$$

Then,

$$\vert E(A, B) \rvert= \sum_i \lambda_i\alpha_i \beta_i$$

What is $\lambda_1$, $\alpha_1, \beta_1$?

After computing eigenvector (eigenvalues) of a d-regular graph, we will obtain that

$$\lambda_1 = d, q_1 = (1/\sqrt{n}, \cdots,1/\sqrt{n})$$

It is not that obvious. Let us prove that.

Formally, we need to prove the following lemma.

$\textbf{Lemma}$. Given a $d$-regular graph, we have two properties on the eigenvalues:

• $\lambda_1 = d$, $u_1 = (/1/\sqrt{n}, \cdots, 1/\sqrt{n})$
• $\lvert \lambda_i \rvert\leq d$ for all $i$.

$\textbf{Proof}$.

The first property can be check by the definition, $Au_1 = \lambda_1 u_1$. It is true.

For the second property, we have the following.

$$A u_x = \lambda u_x \\ \sum_{j}a_{i,j} u_x = \lambda u_x\\$$

Then, we have

$$\lvert \lambda_i \rvert\lvert u_x \rvert = \left\lvert \sum_j a_{i,j} u_x \right\rvert \\ \leq \sum_j \lvert a_{i,j} u_x\rvert \\ =\sum_j a_{i,j}\lvert u_x \rvert \\ \leq d \lvert u_x \rvert$$

So, $\lvert\lambda_i \rvert\leq d$.

We get $\alpha_1 = <\alpha_1, q_1> = \frac{\lvert S \rvert}{\sqrt{n}}$.

Similarly, we get $\beta_1 = \frac{\lvert A \rvert}{\sqrt{n}}$

Since $\lambda_1 = d$, $\alpha_1 = \frac{\lvert A \rvert }{\sqrt{n}}, \beta_1 = \frac{\lvert B \rvert }{\sqrt{n}}$,

$\lambda_1 \alpha_1 \beta_1 = d\frac{\lvert A \vert \lvert B\rvert}{n}$.

In the following, we only need to look at

$$\sum_{i=2}^n \lambda_i \alpha_i \beta_i$$

By Cauchy-Schwarz Inequality which is

$$\lvert \langle u, v\rangle \lvert = \lVert u \rVert \lVert v \rVert$$

we have $\sum_{i=2}^n \lambda_i \alpha_i \beta_i \leq \lambda \sum_{i=2}^n \alpha_i \beta_i \leq \lambda \sqrt{\lvert A \rvert \lvert B \rvert}$

Then, it is proved.

Reference

[1]. Hoory, S., Linial, N. and Wigderson, A., 2006. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4), pp.439-561.