扩展图

在组合数论中，扩展图（英語：Expander graph）是一种具有强连通性质的疏松图，具体而言，看可用边、顶点或图谱扩展性（expansion）三种方式定义。扩展图的构造问题引导了多个数学分支上的研究，它还在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。

定义

简而言之，扩展图是一个有限无向多重图，其中每一组不「太大」的顶点均具有「很大」的边界（boundary）。不同的具体定义给出了不同种类的扩展图，下文将讨论边扩展图、顶点扩展图和谱扩展图（spectral expander）三个概念。

非连通图不是扩展图，因为每一个连通分量都没有边界——分量周围没有边进出，每一个连通图都是扩展图，只是他们的扩展性强弱不同。完全图具有最强的扩展性，但却很稠密（dense）。一个好的扩展图应具有强扩展性，并且顶点度数较小。

边扩展度

包含 $n$ 个顶点的图 $G$ 的边扩展度 $h(G)$ 定义为

$h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},$

其中 $\partial S:=\{(u,v)\in E(G)\ :\ u\in S,v\in V(G)\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)$ 是集合 $S$ 的外边缘，即所有不在 $S$ 中但与一个 $S$ 中的顶点相邻的顶点。顶点扩展度这一概念的一个变体称作「唯一邻点扩展度」（unique neighbor expansion），在这里 $\partial _{\text{out}}(S)$ 指全部仅有一个相邻顶点在 $S$ 中的顶点。

参考来源

教科书和文献综述

• 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, doi:10.1090/S0273-0979-06-01126-8 
• 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