2. Expandermixing 引理

现在我们来讨论一类特殊的图, 叫做 expander , 它们具有非常强的 discrepancy 性质.

定理 2.1 (Expander mixing 引理). 令 $G$ 是一个 $n$ 个点, $d$-正则的图, 并且令它的邻接矩阵的特征值为 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$. 令 $\lambda =\max \{|{\lambda }_2|,|{\lambda }_n|\}$. 那么对于所有的 $X,Y\subseteq V(G)$, 我们有$$\left|e(X,Y)-\frac{d}{n}|X||Y|\right|\le \lambda \sqrt{|X||Y|}.$$

证明. 令 $J$ 是全壹矩阵, 我们有$$\begin{array}{rl}\left|e(X,Y)-\frac{d}{n}\right|X||Y||& =\left|1_X^T\left(A_G-\frac{d}{n}J\right)1_Y\right|\\ & \le \Vert A_G-\frac{d}{n}J\Vert \left|1_X\right|\left|1_Y\right|\\ & =\Vert A_G-\frac{d}{n}J\Vert \sqrt{|X||Y|}.\end{array}$$

接下来只要证明 $A_G-\frac{d}{n}J$ 的最大特征值至多是 $\lambda$ 即可.

令 $v$ 是 $A_G$ 的一个特征向量. 因为 $G$ 是 $d$-正则的, $v$ 可以等于 $\text{mathbbm}1$, 此时对应的特征值是 $d$. $\text{mathbbm}1$ 也是 $A_G-\frac{d}{n}J$ 的一个特征向量, 对应的特征值为 $0$. 如果 $v\ne \text{mathbbm}1$, 那么它与 $\text{mathbbm}1$ 正交, 也就是说 $v\cdot \text{mathbbm}1={\sum }_{i=1}^n{v}_i=0$. 从而, $Jv=0$, 所以 $v$ 也是 $A_G-\frac{d}{n}J$ 的一个特征向量, 并且对应着与它相对于 $A_G$ 一样的特征值. 那么 $A_G-\frac{d}{n}J$ 的特征值就是 $0,{\lambda }_2,{\lambda }_3,\dots ,{\lambda }_n$, 所以它最大的特征值就是 $\lambda$.

$\square$

Expander 与伪随机图之间具有联系: 它们都满足, 当你有一个比较小的顶点集合的时候, 你会期望它们有许多相连的邻居. ¹这种图被叫做 expander 的原因是, 图中大部分的点都能快速的通过这些邻居到达.

我们接下来把我们的注意力集中到一类特殊的图上.

定义 2.2. 一个 $(n,d,\lambda )$-图是一个满足如下条件的图:

1.	它有 $n$ 个点并且是 $d$-正则图.
2.	它的邻接矩阵的特征值是 $d={\lambda }_1\ge \cdots \ge {\lambda }_n$, 并且满足 $\max \{|{\lambda }_2|,|{\lambda }_n|\}\le \lambda$.

Expander mixing 引理 (定理 2.1) 可以等价的表述成: 如果 $G$ 是一个 $(n,d,\lambda )$-图, 那么对于任意的 $X,Y\subset V(G)$,

$$\left|e(X,Y)-\frac{d}{n}|X||Y|\right|\le \lambda \sqrt{|X||Y|}.$$

一个随机图以高概率满足伪随机的性质. 但是我们希望得到伪随机性的确定性构造, 下面是一个这样的构造的例子.

定义 2.3. 令 $\Gamma$ 是一个有限群, 而 $S\subset \Gamma$ 是一个满足 $S=S^{-1}$ 的子集. Cayley 图 $\mathrm{Cay}(\Gamma ,S)=(V,E)$ 的定义为点集 $V=\Gamma$, 并且边集

$$E=\{(g,gs):g\in \Gamma ,s\in S\}.$$

例 2.4. Paley 图是一个 $\mathrm{Cay}(\mathbb{Z}/p\mathbb{Z},S)$ 图, 这里 $p\equiv 1\mathrm{mod}4$ 是一个质数, 而 $S$ 是所有 $\mathbb{Z}/p\mathbb{Z}$ 中的非零二次剩余.

命题 2.5. Paley 图 $G=\mathrm{Cay}(\mathbb{Z}/p\mathbb{Z},S)$ 满足 $|{\lambda }_2|,|{\lambda }_p|\le \frac{\sqrt{p}+1}{2}$, 这里 ${\lambda }_1,\dots ,{\lambda }_p$ 是它的邻接矩阵的特征值.

证明. 我们直接列出它的特征向量. 令顶点 $0$ 对应第一维坐标, 顶点 $1$ 对应第二维坐标, 以此类推.

$$\begin{array}{rl}{v}_1& =(1,\dots ,1)\\ v_2& =\left(1,\omega ,{\omega }^2,\dots ,{\omega }^{p-1}\right)\\ v_3& =\left(1,{\omega }^2,{\omega }^4,\dots ,{\omega }^{2(p-1)}\right)\\ ⋮& \\ v_p& =\left(1,{\omega }^{p-1},\dots ,{\omega }^{(p-1)(p-1)}\right)\end{array}$$

这里 $\omega$ 是 $p$ 次单位根.

我们先验证这些都确实是特征向量. 全壹向量 $v_1$ 的特征值是 $d={\lambda }_1$. 我们算出来 $A_G{v}_2$ 的第 $j$ 维坐标是$$\sum _{s\in S}{\omega }^{j+s}={\omega }^j\sum _{s\in S}{\omega }^s.$$

因为 ${\omega }^j$ 是 $v_2$ 的第 $j$ 维坐标, 所以 $v_2$ 对应的特征值就是 ${\sum }_{s\in S}{\omega }^s$. 一般的, 对于任意的 $0\le k\le p-1$, $${\lambda }_{k+1}=\sum _{s\in S}{\omega }^{ks}.$$值得注意的是, 这是 $\mathbb{Z}/p\mathbb{Z}$ 上的 Cayley 图都具有的性质, 并且这些特征向量与 $S$ 的选取无关. 接下来, 我们来计算每个 ${\lambda }_i$ 的大小. 对于任意 $k>0$, 我们有$$2{\lambda }_{k+1}+1=\sum _{a\in \mathbb{Z}/p\mathbb{Z}}{\omega }^{k{a}^2}.$$

这里我们用到了 $S$ 是所有二次剩余的集合的性质. 等式右边的和被称作高斯和, 我们可以这样求:

把等式右边平方, 得到$${\left|\sum _{a\in \mathbb{Z}/p\mathbb{Z}}{\omega }^{k{a}^2}\right|}^2=\sum _{a,b\in \mathbb{Z}/p\mathbb{Z}}{\omega }^{k\left((a+b{)}^2-a^2\right)}=\sum _{a,b\in \mathbb{Z}/p\mathbb{Z}}{\omega }^{k\left(2ab+b^2\right)}.$$

如果 $b\ne 0$, 那么 $k(2ab+b^2)$ 在固定 $b$, 让 $a$ 遍历 $\mathbb{Z}/p\mathbb{Z}$ 时, 是 $\mathbb{Z}/p\mathbb{Z}$ 的一个重排, 所以

$$\sum _{a\in \mathbb{Z}/p\mathbb{Z}}{\omega }^{k\left(2ab+b^2\right)}=0$$

如果 $b=0$, 那么

$$\sum _{a\in \mathbb{Z}/p\mathbb{Z}}{\omega }^{k(2ab+b^2)}=p.$$

因为高斯和的平方等于 $p$, 所以说 ${\lambda }_{k+1}=\frac{\pm \sqrt{p}-1}{2}$ (对于任意的 $k>0$) .

$\square$

你也许认出了 ${\sum }_{s\in S}{\omega }^{ks}$ 是 $S$ 的指示函数 ($f(s)=1$ 当且仅当 $s\in S$, 否则 $f(s)=0$, 其中 $s\in \mathbb{Z}/p\mathbb{Z}$) 的 Fourier 系数. 事实上, 在定义在 Abel 群上的 Cayley 图的特征值与这个群的 Fourier 变换之间, 有着很紧密的联系. 事实上这两个谱只相差一个常数倍 (这也是我们对特征值和 Fourier 变换都用 “谱” 这个说法的原因) . 对非 Abel 群来说, 情况也差不多, 虽然非 Abel 群的 Fourier 变换就需要表示论了.