Alon–Boppana 界是图的 Laplace 算子次小特征值的一个上界.
定理与证明
设无向图 G=(V,E) 各顶点的度至多为 d, 且有两条边相距至少 2k. 设 λ 为 G 的 Laplace 算子(Δf)(v)=d(v)f(v)−uv=e∈E∑f(u)在子空间 {f:∑v∈Vf(v)=0} 上的最小特征值. 则λ≤d−2d−1+k2d−1−1.
证明. 由于
Δ 半正定, 只需举出函数
f 满足
v∈V∑f(v)=0,⟨f,f⟩⟨Δf,f⟩≤d−2d−1+k2d−1−1.设定理陈述中两条边的顶点集分别为
U0,
V0, 并以
Ui 记离
U0 距离为
i 的顶点的集合, 以
Vi 记离
V0 距离为
i 的顶点的集合, 则由条件, 点集
i=0⋃k−1Ui,i=0⋃k−1Vi无交, 且二者之间没有连边. 另外对
i>0 总有
∣Ui∣≤(d−1)∣Ui−1∣,∣Vi∣≤(d−1)∣Vi−1∣.令
fU=i=0∑k−1(d−1)i/21Ui,fV=i=0∑k−1(d−1)i/21Vi,其中
1 表示
指示函数. 取
f=afU−bfV 为二者的适当线性组合使得
∑v∈Vf(v)=0, 其中
a,b∈R+. 记
A1=a2i=0∑k−1(d−1)i∣Ui∣,B1 为同样的式子将
a,U 换成
b,V. 则
⟨f,f⟩=A1+B1. 记
A2=a2(i=0∑k−2∣Ui∣(d−1)((d−1)i/21−(d−1)(i+1)/21)2+∣Uk−1∣(d−1)((d−1)(k−1)/21)2),B2 类似. 则由条件不难发现
⟨Δf,f⟩=uv=e∈E∑(f(u)−f(v))2≤A2+B2,故只需证
A1+B1A2+B2≤d−2d−1+k2d−1−1,为此只需证
A2/A1 和
B2/B1 皆不大于上式右边. 而
a2A2=i=0∑k−1(d−1)i∣Ui∣(d−2d−1)+(d−1)k−1∣Uk−1∣(2d−1−1)≤a2A1(d−2d−1+k2d−1−1),因为数列
∣Ui∣(d−1)−i 关于
i 单调不增;
B2/B1 类似. 定理得证.
设 {Gn=(Vn,En)}n∈N 是一列有限图, 满足各顶点的度至多为 d, 且 limn→∞∣Vn∣=+∞. 以 λ(Gn) 记 Gn 的 Laplace 算子的次小特征值. 则n→∞limsupλ(Gn)≤d−2d−1.
证明. 由于
Gn 各顶点的度至多为
d, 点数又趋于无穷, 其直径必然趋于无穷. 故定理
1.1 式子中第三项趋于
0.
设 G 是 d-正则图, 以 A 记 G 的邻接矩阵, 则 Δ=d−A, 定理 1.1 相当于说 A 的次大特征值不小于 2d−1−k2d−1−1.
相关概念
Alon–Boppana 界 • 英文 Alon–Boppana bound