擴展圖

在組合數學中，擴展圖（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