扩张图

形式陈述 ​

设 $G=(V,E)$ 是有限简单无向图。对 $S\subseteq V$，边边界定义为

$${\partial }_{E}S=\{\{u,v\}\in E:u\in S,v\notin S\}.$$

图的边扩张常数是

$$h(G)=\underset{0<|S|\le |V|/2}{min}\frac{|{\partial }_{E}S|}{|S|}.$$

也可用外部顶点边界

$${\partial }_{V}S=\{v\in V\setminus S:\mathrm{\exists }u\in S,\{u,v\}\in E\}$$

定义顶点扩张 $h_V(G)=min|{\partial }_{V}S|/|S|$。两者都要求明确边界类型与分母；数值不能在不同规范间直接比较。

若每个顶点度数都是 $d$，称 $G$ 为 $d$-正则图，此时常把 $h(G)$ 除以 $d$ 得到无量纲归一化边扩张。真正的扩张图族是一列图 $(G_n)$，满足 $|V(G_n)|\to \mathrm{\infty }$，存在与 $n$ 无关的常数 $d,\epsilon >0$，使每个 $G_n$ 的最大度数至多 $d$，且 $h(G_n)\ge \epsilon$。若只讨论单张图，只能说它的扩张常数多大，不能省略图族中的规模增长与统一下界。

直觉 ​

扩张要求任何不超过半数的顶点集合都必须向外连接许多边。这样的图没有狭窄瓶颈：从一个小集合开始，每走一步都会接触显著数量的新区域。关键之处是同时保持稀疏与高度连通；完全图连接极强却使用二次量级的边，而扩张图族用常数度数实现近似的全局可达性。

普通连通性公理库图连通性Graph connectivity任意两顶点之间都存在路时图连通。只排除边界为零的非平凡集合，对边界究竟有多小不作约束。扩张把“能否切开”加强为“切开要付出多少边”，因而能区分一条细长的环与一张没有明显瓶颈的稀疏网络。

例子与边界 ​

完全图 $K_n$ 对 $|S|=s\le n/2$ 有 $|{\partial }_{E}S|=s(n-s)$，所以

$$\frac{|{\partial }_{E}S|}{|S|}=n-s\ge \lceil n/2\rceil .$$

它是高扩张的单图，却不是常数度扩张图族，因为度数 $n-1$ 随规模增长。这个例子说明高扩张本身不等于“稀疏而高连通”。

环 $C_n$ 连通且度数恒为 $2$，但取连续的 $\lfloor n/2\rfloor$ 个顶点只暴露两条边，因此

$$h(C_n)\le \frac{2}{\lfloor n/2\rfloor }⟶0.$$

所以环族不是扩张图族。星图则具有很短直径，却有最大度数随 $n$ 增长；它提醒我们，单独的小直径也不能替代“有界度加统一扩张”这两个条件。

推论与应用 ​

若有界度图族具有统一正的顶点扩张，下述增长过程会在 $O(\log n)$ 层内覆盖常数比例的顶点，进而导出对数级直径。边扩张还与随机游走的瓶颈、混合速度及 Laplacian 谱隙定量相关，但这些结论需要固定归一化后由 Cheeger 型不等式连接，不能把谱隙直接写进组合定义。

扩张图在随机算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。中提供少随机性的快速混合结构，在纠错码中把局部约束传播为全局距离，在伪随机性、网络路由和复杂度理论中则用稀疏连接模拟接近完全图的信息扩散。应用依赖的是一族可扩展图，而不是某一张看起来“边很多”的图。

参考资料

• Shlomo Hoory, Nathan Linial, and Avi Wigderson, “Expander Graphs and Their Applications,” Bulletin of the AMS 43 (2006), 439–561.
• Daniel A. Spielman, Spectral and Algebraic Graph Theory, Yale lecture notes, chapters on expansion and conductance.