Expanders 组合视角：有着较好的连通性的图 概率视角：随机游走能迅速混合的图 代数视角：有着较大的谱间隔的图 设G为d-正则图，并令d=a1≥a2≥…≥an≥-d为其邻接矩 阵的特征值. 接下来，我们关注其谱半径spectral radius a :max{a2,an 如果a远小于d,我们说图G有比较好的spectral expansion.Expanders • 组合视角: 有着较好的连通性的图 • 概率视角: 随机游走能迅速混合的图 • 代数视角: 有着较大的谱间隔的图 设G为d-正则图, 并令� = �' ≥ �$ ≥ ⋯ ≥ �8 ≥ −� 为其邻接矩 阵的特征值. 接下来，我们关注其谱半径(spectral radius), � ≔ max{�$, |�4|} 如果 � 远小于�, 我们说图 G 有比较好的spectral expansion