4. Alon–Boppana 界

在一个 $(n,d,\lambda )$ 图中, $\lambda$ 越小, 那么这个图就越伪随机 (译者注: 见 Expander Mixing 引理) . 随之而来的一个问题是, 对于一个确定的 $d$, $\lambda$ 最小可以有多小? 对此我们有 Alon-Boppana 界.

定理 4.1 (Alon-Boppana 界). 对于一个确定的 $d$, 如果 $G$ 是一个 $n$ 个点的图, 并且邻接矩阵 $A_G$ 的特征值是 ${\lambda }_1\ge \cdots \ge {\lambda }_n$, 那么$${\lambda }_2\ge 2\sqrt{d-1}-o(1).$$

随着 $n$ 趋于无穷, 这里低阶项 $o(1)$ 会趋于 $0$.

证明. 令 $V=V(G)$. 根据 Courant-Fischer 定理, 我们只要证明存在一个向量 $z\in {\mathbb{R}}^V-\{0\}$, 使得 $⟨z,1⟩=0$ 并且$$\frac{z^{T}Az}{z^{T}z}\ge 2\sqrt{d-1}.$$

令 $r\in \mathbb{N}$. 任选一个 $v\in V$, 令 $V_i$ 是离 $v$ 距离为 $i$ 的点的集合 ($V_0=\{v\}$, $V_1=N(v)$) . 令 $x\in R^V$ 是这样的向量: $$x_u=w_i:=(d-1{)}^{-i/2}\text{for}u\in V_i,0\le i\le r-1,$$并且对于 $dis(u,v)\ge r$ 的 $u$, $x_u=0$. 我们接下来会证明$$\begin{array}{r}\frac{x^{T}Ax}{x^{T}x}\ge 2\sqrt{d-1}\left(1-\frac{1}{2r}\right).\end{array}$$

为了证明它, 我们要计算$$x^{T}x=\sum _{i=0}^{r-1}|V_i|w_i^2$$

以及$$\begin{array}{rl}{x}^{T}Ax& =\sum _{u\in V}{x}_u\sum _{u^{\prime }\in N(u)}{x}_{u^{\prime }}\\ & \ge \sum _{i=0}^{r-1}|V_i|w_i(w_{i-1}+(d-1)w_{i+1})-(d-1)|V_{r-1}|w_{r-1}{w}_r\\ & =2\sqrt{d-1}\left(\sum _{i=0}^{r-1}|V_i|w_i^2-\frac{1}{2}|V_{r-1}|w_r^2\right)\end{array}$$

其中的不等式成立的原因是 $u\in V_i$ 的每个邻居离 $v$ 的距离都至多是 $i+1$, 并且至少一个邻居的距离是 $i-1$ (注意 $w_i$ 是单调递减的) . 但是因为一旦距离 $\mathrm{dist}(u^{\prime },v)\ge r$, 就会有 $x_{u^{\prime }}=0$, 所以我们必须再减去 $(d-1)|V_{r-1}|w_{r-1}{w}_r$. 再带入 $w_i$ 的定义就得到了上面的式子. 注意因为 $V_{i+1}\le (d-1)|V_i|$, 所以 $|V_{r-1}|\le |V_i|(d-1{)}^{r-i-1}$, 从而 $|V_{r-1}|\ge \frac{1}{r}{\sum }_{i=0}^{r-1}|V_i|w_i^2$, 上面的式子

$$\ge 2\sqrt{d-1}\left(\sum _{i=1}^{r-1}|V_i|w_i^2\right)\left(1-\frac{1}{2r}\right)$$

这就证明了 (4). 但是我们需要有 $⟨z,1⟩=0$. 如果 $n>1+(d-1)+(d-1{)}^2+\cdots +(d-1{)}^{2r-1}$, 那么就一定存在距离至少 $2r$ 的两个顶点 $u,v\in V(G)$. 令 $x\in {\mathbb{R}}^V$ 是以顶点 $v$ 为中心时的这个构造. 让 $y\in {\mathbb{R}}^V$ 是以 $u$ 为中心时的这个构造. 那么 $x$ 和 $y$ 的非零位置是不相交的, 并且对应的两个点集之间也没有边. 也就是说 $x^{T}Ay=0$.

选择一个常数 $c\in \mathbb{R}$, 使得 $z=x-cy$ 满足 $⟨z,q⟩=0$. 那么

$z^{T}z=x^{T}x+c^2{y}^{T}y$

并且

$z^{T}Az=x^{T}Ax+c^2{y}^{T}Ay\ge 2\sqrt{d-1}\left(1-\frac{1}{2r}\right)z^{T}z$.

随着 $n\to \infty$, 相应地令 $r\to \infty$, 我们就证明了这个定理.

$\square$

我们再给出第二种证明方法, 它只能证明一个弱一点的结论, 但是与定理 4.1 表达的意思是一致的.

弱一点的结论. 我们将会证明 $\max \{|{\lambda }_2|,|{\lambda }_n|\}\ge 2\sqrt{d-1}-o(1)$. 这是一个运用迹方法的例子, 这个方法也叫矩方法. 我们有

$$\sum _{i=1}^n{\lambda }_i^{2k}=\mathrm{tr}(A^{2k})$$

等式右边是长度为 $2k$ 的回路个数. 接下来注意到, $d$-正则图里, 从点 $v$ 开始的长度为 $2k$ 的回路个数至少等于一个无限大的 $d$-正则的树里的回路个数. 这是因为, 在一个无限大 $d$-正则的树里的每个回路, 放在图 $G$ 里一样是一个回路, 但是因为 $G$ 里面包含一些环, 所以它还包含了一些额外的回路.

在无限大的 $d$-正则树里, 至少有 $C_k(d-1{)}^k$ ($C_k=\frac{1}{k+1}\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$ 是第 $k$ 个卡特兰数) 条长为 $2k$ 的回路. 所以在 $G$ 里, 至少有 $\frac{n}{k+1}\left(\genfrac{}{}{0ex}{}{2k}{k}\right)(d-1{)}^k$ 条长度为 $2k$ 的回路. 另一方面,

$$d^{2k}+(n-1){\lambda }^{2k}\ge \sum _{i=1}^n{\lambda }_i^{2k}$$

所以,

$${\lambda }^{2k}\ge \frac{1}{k+1}\left(\genfrac{}{}{0ex}{}{2k}{k}\right)(d-1{)}^k-\frac{d^{2k}}{n}.$$

其中 $\frac{1}{k+1}\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$ 这一项在 $k\to \infty$ 的时候是 $(2-o(1){)}^{2k}$. 随着 $n\to \infty$, 令 $k\to \infty$, 并且 $k=o(\log n)$, 我们既可以得到 $\lambda \ge 2\sqrt{d-1}-o(1)$.

$\square$

注 4.2. 注意 $2\sqrt{d-1}$ 是无限大 $d$-正则的树的谱半径 (spectral radius) .