扩展图

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

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

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

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

边扩展性

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

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

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

顶点扩展性

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

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}}}$ 

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

谱扩展性

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

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

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

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

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

Cheeger不等式

对于d-正则图，Dodziuk^[6]和Alon、Milman^[7] 证明了

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

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

• 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