扩展图

在组合数学中，扩展图（Expander graph）是一种具有强连通性质的稀疏图，可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。

## 定义

对于有限、无向、连通的多重图，扩展性是一种能够衡量其连通强弱的指标。直观而言，扩展性较强意味着图中任何“不太大”的顶点集均有较大的边界，也就是说集合内外的交互很强。

连通图的扩展性有的弱，有的强。例如道路的扩展性很弱，而完全图的扩展性最强。可以看出，稠密图比稀疏图更“容易”具备强扩展性。但人们希望构造一类鱼与熊掌兼得的图：既能保持稀疏性，又具备很强的扩展性。具备这样“矛盾”属性的图就是一张扩展图；矛盾对立越深，扩展图越优良。

用数学语言表达如下：若一张图图有 $n$ 个顶点、最大度为 $d$、扩展性为 $h$，那么就称它为$(n,d,h)$-扩展图。$d$ 越小（即图越稀疏）且 $h$ 越大（即扩展性越强），则扩展图的性质越优异。

作为扩展图定义中的关键参数之一，“扩展性”的精确概念可用不同方式来量化。下文将讨论边扩展性、顶点扩展性和谱扩展性三种量化方式。

### 边扩展性

包含 $n$ 个顶点的图 $G = (V,E)$ 的边扩展性 $h(G)$ 定义为

$$h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial S|}{|S|}$$

其中 $\partial S := \{ \{u,v\} \in E \mid u \in S, v \in V \setminus S \}$ 为子集 $S$ 的边界。注意在此定义中，最小值取于所有非空且大小不超过 $n/2$ 的顶点集。

### 顶点扩展性

图 $G$ 的顶点扩展性 $h_{\text{out}}(G)$ 定义为

$$h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}$$

此处 $\partial_{\text{out}}(S) := \{v \not\in S \mid \exists u \in S: \{u,v\} \in E\}$ 是集合 $S$ 的外边缘。顶点扩展性有一种变体，称作“唯一邻点扩展性”（unique neighbor expansion），在这里 $\partial_{\text{out}}(S) := \{v \not\in S \mid \exists! u \in S: \{u,v\} \in E\}$。

### 谱扩展性

当 $G$ 是d-正则图时，可以借助线性代数中的特征值理论来定义扩展性，称作谱扩展性。具体而言，设 $A$ 是图 $G$ 的邻接矩阵，其中 $A(i,j)$ 记录了顶点 $i, j$ 之间的边数。因为 $A$ 是实对称矩阵，根据谱定理知道它有 $n$ 个实特征值 $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_{n}$。可以证明它们都落在区间 $[-d,d]$内。

由于 $G$ 是正则图，所以 $\mathbb{R}^n$ 上的均匀分布 $\mathbf{u} := (1/n, 1/n, \dots, 1/n)$ 是矩阵 $A$ 的特征向量，对应特征值 $d = \lambda_1$，即 $A\mathbf{u} = d\mathbf{u}$。图 $G$ 的谱间距（spectral gap）定义为 $d - \lambda_2$，它可以用作扩展性的量度。

## 三种扩展性度量之间的关系

上面定义的三种量化方式虽然形式上有差别，但在本质上相互联系。对于d-正则图，我们有

$$h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G).$$

因此，当度是常数时，前两种量化方式并无实质区别。

### Cheeger不等式

对于d-正则图，Dodziuk和Alon、Milman 证明了

$$\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}$$

这一不等式与马尔可夫链的Cheeger不等式有本质联系。

上界

上界则（渐近地）由环 $C_n$ 达到，其中$h(C_n) = 4/n = \Theta(1/n)$。

而 $d - \lambda_2 = 2 - 2\cos(2\pi/n) \approx (2\pi/n)^2 = \Theta(1/n^2)$。

此外，文献给出了更紧的上界：

$$h(G) \le \sqrt{d^2 - \lambda_2^2}$$

下界

事实上，此下界是紧的。以超立方体 $Q_n$ 为例。

其正则度为 $d = n$，且其特征值为$\lambda_k = n - 2k$（$k = 0, 1, \ldots, n$）。

故第二大特征值为 $\lambda_2 = n - 2$。

谱隙为 $d - \lambda_2 = 2$，下界为 $\tfrac{1}{2}(d - \lambda_2) = 1$。

又 $h(Q_n) = 1$，因此无论维度 $n$ 为何，下界恰好取等。

这些不等式与马尔可夫链的Cheeger bound密切相关。

也可视为黎曼几何中Cheeger不等式的离散版本。

类似地，顶点等周数与谱隙之间的关联也已被研究

$$h_{\text{out}}(G) \le \sqrt{(4(d - \lambda_2) + 1)^2 - 1}$$

$$h_{\text{in}}(G) \le \sqrt{8(d - \lambda_2)}$$

渐近而言，$h^2/d$、$h_{\text{out}}$ 与 $h_{\text{in}}^2$ 均以谱隙 $O(d - \lambda_2)$ 为上界。

## 构造策略

要实际构造出扩展图家族，目前有四种主要策略。

在介绍各种构造方法之前，先定义构造的目标——Ramanujan图。

(1) 代数与群论

(2) 分析方法，使用堆垒数论

(3) 组合方法，使用锯齿积及相关图积

(4) 覆盖图（又称 lift）

### Margulis–Gabber–Galil

基于凯莱图的代数构造适用于扩展图的各种变体。

以下构造由 Margulis 提出，并由 Gabber 与 Galil 分析。

对每个自然数 $n$，考虑顶点集为 $\mathbb{Z}_n \times \mathbb{Z}_n$ 的图$G_n$。

其中 $\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$。

对每个顶点 $(x, y) \in \mathbb{Z}_n \times \mathbb{Z}_n$。

其八个相邻顶点为

$$\{(x \pm 2y,\ y),\quad (x \pm (2y+1),\ y),\quad (x,\ y \pm 2x),\quad (x,\ y \pm (2x+1))\}.$$

则有以下定理：

定理：对所有 $n$，图 $G_n$ 的第二大特征值满足 $\lambda(G_n) \le 5\sqrt{2}$。

### Ramanujan图

由 Alon–Boppana定理，所有足够大的 d-正则图均满足

$$\lambda_2 \ge 2\sqrt{d-1} - o(1)$$

其中 $\lambda_2$ 为绝对值意义下的第二大特征值。

可直接得出：对每个固定的 $d$ 与 $\lambda < 2\sqrt{d-1}$。

满足条件的 $(n, d, \lambda)$-图仅有有限个。

Ramanujan graph是使上述界恰好取等的 d-正则图，满足

$$\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1}$$

因此 Ramanujan 图的 $\lambda_2$ 在渐近意义下达到最小可能值，是极佳的谱扩展图。

Lubotzky、Phillips 与Sarnak（1988年）、Margulis（1988年）

及 Morgenstern（1994年）给出了 Ramanujan 图的显式构造。

1985年，Alon 猜测：对足够大的 $n$，大多数顶点数为 $n$ 的 d-正则图是“几乎 Ramanujan”的。

即对任意 $\varepsilon > 0$，其非平凡特征值满足

$$\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1} + \varepsilon$$

2003年，Joel Friedman 证明了此猜想，并明确了“大多数 d-正则图”的含义：

随机正则图以概率 $1 - O(n^{-\tau})$ 满足上式，其中

$$\tau = \left\lceil \frac{\sqrt{d-1}+1}{2} \right\rceil$$

Puder 随后给出了稍弱结果的更简短证明。

#### 例子

- 完全图 $K_4$ 是 3-正则 Ramanujan 图。

其非平凡特征值均为 $-1$。

满足 $|-1| = 1 \le 2\sqrt{2} = 2\sqrt{d-1}$。

- 佩特森图是 3-正则 Ramanujan 图。

其邻接矩阵 $A$ 满足 $A^2 = 2I + J - A$。

故 $\mathbf{1}^\perp$ 上的非平凡特征值满足$\lambda^2 + \lambda - 2 = 0$。

解得 $\lambda \in \{1, -2\}$。

均满足 $|\lambda| \le 2 = 2\sqrt{d-1}$。

### 锯齿积

Reingold、Vadhan 与Wigderson 于 2000 年引入了锯齿积。

粗略来说，两个扩展图的锯齿积产生一个扩展性仅略差的新图。

因此锯齿积也可用于构造扩展图族。

若 $G$ 是 $(n, d, \lambda_1)$-图。

$H$ 是 $(m, d, \lambda_2)$-图。

则锯齿积 $G \circ H$ 是 $(nm, d^2, \varphi(\lambda_1, \lambda_2))$-图。

其中 $\varphi$ 具有以下性质：

- 若 $\lambda_1 < 1$ 且 $\lambda_2 < 1$，则 $\varphi(\lambda_1, \lambda_2) < 1$。
- $\varphi(\lambda_1, \lambda_2) \le \lambda_1 + \lambda_2$。

具体而言。

$$\varphi(\lambda_1, \lambda_2) = \tfrac{1}{2}(1 - \lambda_2^2)\lambda_1 + \tfrac{1}{2}\sqrt{(1-\lambda_2^2)^2 \lambda_1^2 + 4\lambda_2^2}$$

性质 (1) 说明两个扩展图的锯齿积仍为扩展图。

故可用归纳法，利用锯齿积构造扩展图族。

直观上，锯齿积的构造可理解如下。

将 $G$ 的每个顶点“膨胀”为一个由 $m$ 个顶点组成的“云”。

每个顶点对应该原始顶点的一条边。

新图中每个顶点标记为 $(v, k)$。

其中 $v$ 为 $G$ 的原始顶点，$k$ 为 $v$ 的第 $k$ 条边。

两顶点 $(v, k)$ 与 $(w, \ell)$ 相连。

当且仅当可透过以下步骤从 $(v, k)$ 到达 $(w, \ell)$：

- 锯（Zig）— 沿 $H$ 的一条边从 $(v, k)$ 移动至 $(v, k')$。
- 跳（Jump）— 沿 $G$ 中的第 $k'$ 条边跨越云，到达 $(w, \ell')$。
- 齿（Zag）— 沿 $H$ 的一条边从 $(w, \ell')$ 移动至 $(w, \ell)$。

### 覆盖图（Lift）

图的 $r$-lift 由以下方式构造：将每个顶点替换为 $r$ 个顶点。

并将每条边替换为对应两组 $r$ 个顶点之间的一个完美匹配。

提升后的图继承原图的所有特征值，并额外产生新的特征值。

Bilu 与 Linial 证明了每个 $d$-正则图都存在一个 2-lift。

使得额外特征值的绝对值至多为 $O(d\log^3 d)$。

他们还证明，若起始图是足够好的扩展图，则可在多项式时间内找到良好的 2-lift。

从而对每个 $d$ 给出 $d$-正则扩展图的高效构造。

Bilu 与 Linial 猜测上界 $O(d\log^3 d)$ 可改进为 $2\sqrt{d-1}$。

由 Alon–Boppana定理知此界是最优的。

此猜想在二部图情形下由 Marcus、Spielman 与 Srivastava 证明。

他们使用了交错多项式（interlacing polynomials）方法。

从而给出了二部图 Ramanujan graph的另一种构造。

原本的非构造性证明后来由 Michael B. Cohen 转化为算法。

此后，Hall、Puder 与 Sawin 将此方法推广至 $r$-lift。

此猜想在二部图情形下由 Marcus。

Spielman 与Srivastava 证明。

他们使用了交错多项式（interlacing polynomials）方法。

从而给出了二部图 Ramanujan图的另一种构造。

原本的非构造性证明后来由 Michael B. Cohen 转化为算法。

此后，Hall、Puder 与 Sawin 将此方法推广至 $r$-lift。

2024年，Jiaoyang Huang、Theo McKenzie 与 姚鸿泽 的预印本进一步证明。

非平凡特征值满足

$$\lambda \le 2\sqrt{d-1}$$

并通过证明谱边缘普适性（edge universality）成立（即特征值遵循与高斯正交系综相关的Tracy–Widom分布）。

说明达到 Alon–Boppana 界的特征值比例约为 69%。

### 扩展混合引理

扩展混合引理指出：对于 $(n,d,\lambda)$-图。

对任意两个顶点子集 $S,T \subseteq V$， $S$ 与 $T$ 之间的边数近似于随机 $d$-正则图中的期望值； $\lambda$ 越小，此近似越精确。

在随机 $d$-正则图，以及边几率为 $d/n$ 的Erdős–Rényi随机图中， $S$ 与 $T$ 之间的期望边数为 $\tfrac{d}{n}|S||T|$。

更正式地，设 $E(S,T)$ 表示 $S$ 与 $T$ 之间的边数。

若两集合有交集，则其交集内部的边会被计算两次，也就是

$$E(S,T) = 2|E(G[S \cap T])| + E(S \setminus T,\ T) + E(S,\ T \setminus S).$$

则扩展混合引理断言：

$$\left|E(S,T)-\frac{d|S||T|}{n}\right| \leq \lambda\sqrt{|S||T|}.$$

$(n,d,\lambda)$-图的许多性质都是扩展混合引理的推论，包括以下几点。

- 图的独立集是不含任两相邻顶点的顶点子集。在 $(n,d,\lambda)$-图中，任一独立集的大小至多为 $\lambda n/d$。
- 图 $G$ 的图色数 $\chi(G)$ 是使任两相邻顶点颜色不同所需的最少颜色数。

Hoffman 证明了$d/\lambda \leq \chi(G)$。

而 Alon、Krivelevich 与 Sudakov 证明：若 $d < 2n/3$，则

```
<math>\chi(G) \le O\left(\frac{d}{\log\left(1 + \frac{d}{\lambda}\right)}\right).</math>
```

- 图的直径R是任两顶点之间最短路径长度的最大值。

```
 <math>\operatorname{diam}(G) = \max_{u,v \in V} \operatorname{dist}(u,v)</math>。
```

Chung 证明，$(n,d,\lambda)$-图的直径至多为

```
 <math>\left\lceil {\log \frac{n}{{\log (\frac{d}{\lambda})}}} \right\rceil.</math>
```

## 外部链接

- Brief introduction in Notices of the American Mathematical Society
- Introductory paper by Michael Nielsen
- Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)
- Lecture notes from a course on expanders (by Prahladh Harsha)
- Definition and application of spectral gap