扩张图

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

普通连通性理路图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。只排除边界为零的非平凡集合，对边界究竟有多小不作约束。扩张把“能否切开”加强为“切开要付出多少边”，因而能区分一条细长的环与一张没有明显瓶颈的稀疏网络。

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

其扩张常数随 $n$ 增长，度数 $n-1$ 也随之增长，付出的是二次数量级的边。

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

所以环族不是扩张图族。星图的直径至多为二，但中心度数为 $n-1$；它通过集中在一个枢纽上的连接获得短路径。

若 $h_V(G)\ge \epsilon >0$，从顶点 $v$ 出发，记 $B_k(v)$ 为距离至多 $k$ 的顶点集。当 $|B_k(v)|\le n/2$ 时，

当 $\epsilon$ 与 $n$ 无关时，$O(\log n)$ 层后，球会包含超过半数的顶点。任意两个这样的球必相交，因而图的直径为 $O(\log n)$。

边扩张还衡量随机游走遇到的瓶颈。Cheeger 型不等式在固定归一化后，将扩张常数与 Laplacian 谱隙联系起来，再用于估计混合速度。

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