擴展圖

在組合數學中，擴展圖（英語：Expander graph）是一種具有強連通性質的稀疏圖，可用邊擴展性、頂點擴展性或圖譜擴展性三種方式來量化。擴展圖的構造問題引導了多個數學分支上的研究，並且在計算複雜性理論、計算機網絡設計和編碼理論上有諸多應用。

定義

對於有限、無向、連通的多重圖，擴展性是一種能夠衡量其連通強弱的指標。直觀而言，擴展性較強意味着圖中任何「不太大」的頂點集均有較大的邊界，也就是說集合內外的交互很強。

連通圖的擴展性有的弱，有的強。例如道路的擴展性很弱，而完全圖的擴展性最強。可以看出，稠密圖比稀疏圖更「容易」具備強擴展性。但人們希望構造一類魚與熊掌兼得的圖：既能保持稀疏性，又具備很強的擴展性。具備這樣「矛盾」屬性的圖就是一張擴展圖；矛盾對立越深，擴展圖越優良。

用數學語言表達如下：若一張圖圖有 $n$ 個頂點、最大度為 $d$、擴展性為 $h$，那麼就稱它為$(n,d,h)$-擴展圖。$d$ 越小（即圖越稀疏）且 $h$ 越大（即擴展性越強），則擴展圖的性質越優異。

作為擴展圖定義中的關鍵參數之一，「擴展性」的精確概念可用不同方式來量化。下文將討論邊擴展性、頂點擴展性和譜擴展性三種量化方式。

邊擴展性

包含 $n$ 個頂點的圖 $G=(V,E)$ 的邊擴展性 $h(G)$ 定義為

$h(G)=\min _{0<|S|\leq {\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|\leq {\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}\geq \lambda _{2}\geq \cdots \geq \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)\leq h(G)\leq d\cdot h_{\text{out}}(G).$

因此，當度是常數時，前兩種量化方式並無實質區別。

Cheeger不等式

對於d-正則圖，Dodziuk和Alon、Milman 證明了

${\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}$

這一不等式與馬爾可夫鏈的Cheeger不等式有本質聯繫。

參考來源

教科書和文獻綜述

• Alon, N.; Spencer, Joel H. 9.2. Eigenvalues and Expanders. The Probabilistic Method 3rd. John Wiley & Sons. 2011. 
• Chung, Fan R. K., Spectral Graph Theory, CBMS Regional Conference Series in Mathematics 92, American Mathematical Society, 1997, ISBN 0-8218-0315-8 
• Davidoff, Guiliana; Sarnak, Peter; Valette, Alain, Elementary number theory, group theory and Ramanujan graphs, LMS student texts 55, Cambridge University Press, 2003, ISBN 0-521-53143-8 
• Hoory, Shlomo; Linial, Nathan; Widgerson, Avi, Expander graphs and their applications (PDF), Bulletin (New series) of the American Mathematical Society, 2006, 43 (4): 439–561 [2017-08-16], doi:10.1090/S0273-0979-06-01126-8, （原始內容存檔 (PDF)於2021-01-26） 
• Krebs, Mike; Shaheen, Anthony, Expander families and Cayley graphs: A beginner's guide, Oxford University Press, 2011, ISBN 0-19-976711-4 

研究論文

• Ajtai, M.; Komlós, J.; Szemerédi, E., An O(n log n) sorting network, Proceedings of the 15th Annual ACM Symposium on Theory of Computing: 1–9, 1983, ISBN 0-89791-099-0, doi:10.1145/800061.808726 
• Ajtai, M.; Komlós, J.; Szemerédi, E., Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, 1987: 132–140, ISBN 0-89791-221-7, doi:10.1145/28395.28410 
• Alon, N.; Capalbo, M. Explicit unique-neighbor expanders. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002: 73. ISBN 0-7695-1822-2. doi:10.1109/SFCS.2002.1181884. 
• Bobkov, S.; Houdré, C.; Tetali, P., λ_∞, vertex isoperimetry and concentration, Combinatorica, 2000, 20 (2): 153–172, doi:10.1007/s004930070018 .
• Dinur, Irit, The PCP theorem by gap amplification, Journal of the ACM, 2007, 54 (3): 12–es, doi:10.1145/1236457.1236459 .
• Gillman, D., A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing (Society for Industrial and Applied Mathematics), 1998, 27 (4,): 1203–1220, doi:10.1137/S0097539794268765 
• Goldreich, Oded, Basic Facts about Expander Graphs, Studies in Complexity and Cryptography, 2011: 451–464, doi:10.1007/978-3-642-22670-0_30 
• Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291 
• Yehudayoff, Amir, Proving expansion in three steps, ACM SIGACT News, 2012, 43 (3): 67–84, doi:10.1145/2421096.2421115 

外部連結

• 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