扩展图

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

定义

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

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

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

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

边扩展性

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

$h(G)=\underset{0<|S|\le \frac{n}{2}}{\min }\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)=\underset{0<|S|\le \frac{n}{2}}{\min }\frac{|{\partial }_{\text{out}}(S)|}{|S|}$

此处 ${\partial }_{\text{out}}(S):=\{v\in ̸S\mid \mathrm{\exists }u\in S:\{u,v\}\in E\}$ 是集合 $S$ 的外边缘。顶点扩展性有一种变体，称作「唯一邻点扩展性」（Template:Lang），在这里 ${\partial }_{\text{out}}(S):=\{v\in ̸S\mid \mathrm{\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$ 是正则图，所以 ${ℝ}^n$ 上的均匀分布 $𝐮:=(1/n,1/n,\dots ,1/n)$ 是矩阵 $A$ 的特征向量，对应特征值 $d={\lambda }_1$，即 $A𝐮=d𝐮$。图 $G$ 的谱间距（spectral gap）定义为 $d-{\lambda }_2$，它可以用作扩展性的量度。

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

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

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

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

Cheeger不等式

对于d-正则图，DodziukTemplate:Sfn和Alon、MilmanTemplate:Sfn 证明了

$\frac{1}{2}(d-{\lambda }_2)\le h(G)\le \sqrt{2d(d-{\lambda }_2)}$

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

参考来源

Template:Refbegin 教科书和文献综述

• Template:Cite book
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

研究论文

• Template:Citation
• Template:Citation
• Template:Cite book
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

外部链接

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