Ramanujan 图的顶点扩展性

论文 Better Expansion for Ramanujan Grdphs. Nabil Kahale, 1991 阅读笔记。这篇文章证明了 $d$ 正则 Ramanujan 图的 vertex expansion 为 $\dfrac {d}2$。

给一个 $d$ 正则图为 $G=(V,E)$。考虑邻接矩阵 $A$ 的谱 $d=\lambda_1\ge\lambda_2\ge\ldots$，则 $\lambda_2$ 就给出了 $G$ 的 spectral expansion。

对于 Ramanujan 图（由 Alon-Boppana Bound，即是满足 $\lambda_2\le 2\sqrt{d-1}+o_n(1)$ 的图），vertex expansion 与 spectral expansion 之间有一些关系。

较为简单的一个下界——d/4

先热个身，我们来证明 Ramanujan 图有 $\dfrac d4$ 的 vertex expansion：

对于任何向量 $f\in C(V)\,(C(V):=\{f:V\to\mathbb R\})$，首先由 Cauchy-Schwartz 不等式我们可以得到：

$\left(\sum_{f(i)\ne 0} f^2(i) \right)\left(\sum_{f(i)\ne 0} 1 \right)\ge \left(\sum_{f(i)\ne 0}f(i) \right)^2$

故：

$\text{supp}(f)\ge \dfrac{\|f\|_1^2}{\|f\|_2^2}$

其中 $\text{supp}(f):=\#\{f(v)\ne 0\mid v\in V\}$。

那么对于任意顶点集的子集 $X\subset V$，令 $f=A\bm{1}_X$，则：

$\text{supp}(A\bm{1}_X)=|N(X)|\ge \dfrac{\|A\bm{1}_X\|_1^2}{\|A\bm{1}_X\|_2^2}$

分子是好估计的：$\|A\bm{1}_X\|_1=d|X|$。对于分母我们将 $\bm{1}_X$ 分解成平行于 $\bm{1}$ 的部分 $f^\|$ 与剩下的垂直部分 $f^\bot$，则：

$\|A\bm{1}_X\|_2^2=\|A(f^\|+f^\bot)\|_2^2=\left\|\dfrac{d|X|}{|V|}\bm{1}+Af^\bot \right\|_2^2$

$\le \dfrac{d^2|X|^2}{|V|}+\|\lambda_2f^\bot\|_2^2\le \dfrac{d^2|X|^2}{|V|}+\lambda_2^2\left( |X|-\dfrac{|X|^2}{|V|} \right)$

令 $\alpha=|X|/|V|$，再由 Ramanujan 图性质：$\lambda_2=2\sqrt{d-1}+o(1)$，代入化简得到：

$\dfrac{|N(X)|}{|X|}\ge \dfrac{d^2}{\alpha d^2+\lambda_2^2(1-\alpha)}=\dfrac{1}{\alpha+\frac{4(d+1)+o(1)}{d^2}(1-\alpha)}$

可以发现右边这个函数随着 $\alpha$ 是单调的，取 $\alpha=0,1$ 即可得：

$\dfrac{|N(X)|}{|X|}\ge \max\left\{ \dfrac{d^2}{4(d+1)+o(1)} ,1 \right\}=\max\left\{\dfrac d4-o(1),1\right\}$

主要引理

Main Lemma：设 $G=(V,E)$ 是一个 $d$ 正则图，令 $\bar{\lambda}=\max\{\lambda_2(G),2\sqrt{d-1}\}:=2\sqrt{d-1}\cosh(\theta)\,(\theta\ge0)$，则对于顶点集的任意大小最多为 $d^{-1/\epsilon}{|V|}$ 子集 $X$，我们有：

$\lambda_1(M_X^\theta)\le \bar{\lambda}(1+O(\epsilon))$

其中（下式中 $A_X,\Delta_X$ 分别为 $G[X]$ 的邻接矩阵与度数矩阵）：

$M_X^\theta=A_X+\dfrac{1}{\sqrt{d-1}\exp(\theta)}(dI-\Delta_X)$

也就是生成子图的邻接矩阵再加上一个对角项。

在这一节中我们主要来证明这一 Main Lemma。

值得一提的是，关于 $\cosh(\theta)$ 这一项的引入，本人认为没有什么很本质的原因。大致上的原因就是 $\cosh(\theta)$ 是一个恒大等于 $1$ 的函数，把这一项加在这里方便计算。对于带 $\theta$ 的项，本人认为，都是方便计算存在的，有一堆较为复杂的分式可以说都是从结果反推回来，不过是用 $\theta$ 表示了出来，没有什么本质的含义（有大佬不这么认为可以来和我讨论一下）。

总流程

我们先用下面一个流程图展示一下这一主要引理的证明思路（里面的各种记号在后文中都会定义）：

$\lambda_2(G)\xrightarrow{\text{Lemma }1}\lambda_1(B_l(X))\xrightarrow{\text{Lemma }2}\lambda_1(M_X^{\theta',l})\approx \lambda_1(M_X^\theta)$

第一个箭头

我们先证明如下引理：

Lemma 1：设 $G=(V,E)$ 是一个 $d$ 正则图，则对于顶点集的任何一个子集 $X\subset V$，有：

$\lambda_1(G[X])\le \lambda_2(G)+\dfrac{(d-\lambda_2(G))|X|}{|V|}$

方便起见之后我们都用 $\lambda_{1,2}(X)$ 代指 $\lambda_{1,2}(G[X])$。

Proof：对于任意一个 $f\in C(V)$，还是将其分解为 $f=f^\|+f^\bot$，则有：

$\langle Af,f\rangle=\langle Af^\|,f^\|\rangle+\langle Af^\bot,f^\bot\rangle \le d\|f^\|\|_2^2+\lambda_2(G)\|f^\bot\|_2^2$

$=\lambda_2(G)\|f\|_2^2+(d-\lambda_2(G))\|f^\|\|_2^2 =\lambda_2(G)\|f\|_2^2+\dfrac{d-\lambda_2(G)}{|V|}\left(\sum_{v\in V}f^2(v) \right)^2$

其中最后一步等式转换用到了事实：

$\|f^\|\|_2^2=\dfrac 1{|V|}\left(\sum_{v\in V}f^2(v) \right)^2$

现在假设 $f(v)=0\, ,\forall v\in V\backslash X$，则定义 $g\in C(X)$ 为 $g(v)=f(v)\, ,\forall v\in X$。那么有：$\langle A_X g,g\rangle=\langle Af,f\rangle,\|g\|_2^2=\|f\|_2^2$，于是由上面的结果得：

$\langle A_Xg,g\rangle \le \lambda_2(G)\|g\|_2^2+\dfrac{d-\lambda_2(G)}{|V|}\left(\sum_{v\in X}g^2(v) \right)^2 \le \left(\lambda_2(G)+\dfrac{(d-\lambda_2(G))|X|}{|V|} \right)\|g\|_2^2$

再由 Rayleigh 定理即得证。其中最后一步用了 Cauchy-Schwartz 不等式。$\Box$

这一引理告诉我们可以使用生成子图大小 $|W|$ 和原图的谱隙 $\lambda_2(G)$ 去控制 $\lambda_1(W)$。

这样我们就可以“完成第一个箭头”。

我们定义 $B_l(X)=\{v\mid d(v,X)\le l\}$，也就是距离 $X$ 不超过 $l$ 的点的集合（图上的一个闭圆盘）。则我们有：

$|B_l(X)|\le |X|(d+\cdots+d^l)\le 2 d^l|X|\, (d\ge 2)$

再使用 Lemma 1 就可以用 $\lambda_2(G)$ 表示出 $\lambda_1(B_l(X))$。

第二个箭头

下面这一个引理“完成了第二个箭头”。

Lemma 2：设 $G=(V,E)$ 是一个 $d$ 正则图，$l$ 是一个正整数，$X$ 是顶点集 $V$ 的一个非空子集。给定一个常数 $\lambda'=2\sqrt{d-1}\cosh(\theta')\,(\theta'\ge 0)$，如果 $\lambda_1(B_l(X))\le \lambda'$ 成立，则有 $\lambda_1(M_X^{\theta',l})\le \lambda'$ 亦成立。

其中 $M_X^{\theta',l}$ 被定义为：

$M_X^{\theta',l}:=A_X+\dfrac 1{\sqrt{d-1}}\dfrac{\sinh(l\theta')}{\sinh((l+1)\theta')}(dI-\Delta_X)$

Idea：证明此定理的基本思路是：把 $M_X^{\theta',l}$ 的特征值 $\lambda_1(M_X^{\theta',l})$ 对应的特征向量 $f$，以某种方式扩展为 $C(B_l(X))$ 中的向量 $f'$。又有 Rayleigh 定理，$\langle A_{B_l(X)}f',f' \rangle\le \lambda_1(B_l(X))\|f'\|_2^2\le \lambda' \|f'\|_2^2$，从而得到最后结果。

我们先做一些定义：

$r_i=\dfrac{\sinh((l+1-i)\theta')(d-1)^{-i/2}}{\sinh((l+1)\theta')}\,(1\le i\le l) \\ r_i=0\,(i>l)$

可以发现 $r_i$ 是单调递减的，且有如下递推关系（用双曲三角函数的和差化积即可）：

$\lambda' r_i=r_{i-1}+(d-1)r_{i+1} \\ \lambda' r_l=r_{l-1}$

（对于 $r_i$ 形象的“理解”是：深度为 $l$ 的 $d$ 叉树上，$r_i$ 是“$\lambda'$ 对应的特征向量”中，深度为 $i$ 的点对应 entry）

对于 $M_X^{\theta',l}$ 的特征值 $\lambda_1(M_X^{\theta',l})$ 对应的特征向量 $f$（我们不妨设 $f$ 的所有位置的值都是非负的），我们用如下方式将其扩展为 $C(B_l(X))$ 上的向量 $f'$：

$f'(v)=\begin{cases} f(v) & v\in X \\ \max\limits_{u\in X}\{f(u)r_{d(v,u)}\} & v\in B_l(X)\backslash X \end{cases}$

其中 $d(v,u)$ 表示图上 $v,u$ 间的距离。

我们有如下 Claim：

Claim：我们有如下事实：

1. $\forall v\in B_l(X)\backslash X,\, (A_{B_l(X)}f')(v)\ge \lambda' f'(v)$；
2. $\forall v\in X,\, (A_{B_l(X)}f')(v)\ge \lambda_1(M_X^{\theta',l}) f'(v)$。

Proof of Claim：

② 先来证明第二条：

$(A_{B_l(X)}f')(v)\ge (A_X f)(v)+(d-d_X(v))f(v)r(1)=(M_X^{\theta',l}f')(v)=\lambda_1(M_X^{\theta',l})f'(v)$

得证。

① 再来证明第一条：

对于 $v\in B_l(X)\backslash X$，假设是 $u\in X$ 使得 $f'(v)=f(u)r_{d(v,u)}$，则有 $1\le d(v,u)\le l$。

设 $v_1$ 为从 $v\to u$ 的最短路上除 $v$ 外的第一个点，并令 $i=d(v,u)$，则有：

$f'(v_1)\ge f'(u)r_{i-1}$

我们对 $i$ 的取值进行分类讨论：

(a) 若 $i=l$，则：

$(A_{B_l(X)}f')(v)\ge f(v_1)\ge f'(v)r_{l-1}=\lambda' f'(u)r_l=\lambda' f'(v)$

(b) 若 $i<l$，则 $v$ 的 $d$ 个邻居都在 $B_l(X)$ 中，且除了 $f'(v_1)$，还有 $d-1$ 个邻居上的 $f'$ 值是大等于 $f'(u)\ge f'(u)r_{i+1}$ 的，故：

$(A_{B_l(X)}f')(v)\ge f'(v_1)+(d-1)f'(u)r_{i+1} \\ \ge f'(u)(r_{i-1}+(d-1)r_{i+1})=\lambda' f'(v)r_i\ge \lambda' f'(v)$

故得证。$\Box$

Proof of Lemma 2：有了这么多的铺垫，我们终于可以证明 Lemma 2：

使用反证法：假设 $\lambda_1(M_X^{\theta',l})>\lambda'$，则结合 Claim 中的两条，则有：

$\forall v\in B_l(X),\, (A_{B_l(X)}f')(v)\ge \lambda' f'(v)$

且在 $v\in X$ 的时候，上面的不等号严格成立。

于是乎：$\langle A_{B_l(X)}f',f' \rangle> \lambda' \|f'\|_2^2$，这显然与 $\lambda_1(B_l(X))\le \lambda'$ 矛盾了。$\Box$

主要引理的证明

有了上面几个引理的铺垫，主要引理的证明便呼之欲出了。

Main Lemma：设 $G=(V,E)$ 是一个 $d$ 正则图，令 $\bar{\lambda}=\max\{\lambda_2(G),2\sqrt{d-1}\}:=2\sqrt{d-1}\cosh(\theta)\,(\theta\ge 0)$，则对于顶点集的任意大小最多为 $d^{-1/\epsilon}{|V|}$ 子集 $X$，我们有：

$\lambda_1(M_X^\theta)\le \bar{\lambda}(1+O(\epsilon))$

Proof：令 $l=\lfloor 1/(2\epsilon)\rfloor$，并令 $W=B_l(X)$，则易得：$|W|\le 2d^l|X|\le 2d^{-1/(2\epsilon)}|V|$（这里用到了条件 $|X|\le d^{-1/\epsilon}{|V|}$ 与 $l$ 的表达式）。

则有 Lemma 1 可得：

$\lambda_1(W)\le \lambda_2(G)+\dfrac{(d-\lambda_2(G))|W|}{|V|}\le \bar{\lambda}+2d^{1-1/(2\epsilon)}$

注意这里用到了 $|W|,\bar{\lambda}$ 的表达式。

我们把最右边那堆定义为 $\lambda'=2\sqrt{d-1}\cosh(\theta')$，则由 Lemma 2 可得：

$\lambda_1(M_X^{\theta',l})\le \lambda'$

其实我们已经离结果很近了，我们接下来要证明流程图最右边的 $\approx$，即证明 $\lambda_1(M_X^{\theta',l})$ 与 $\lambda_1(M_X^\theta)$ 相差不多。

注意到：

$M_X^\theta-M_X^{\theta',l}=\dfrac{1}{\sqrt{d-1}}\left(\dfrac{1}{\exp(\theta)}-\dfrac{\sinh(l\theta')}{\sinh((l+1)\theta')}\right)(dI-\Delta_X)$

是对角矩阵，其特征值绝对值大小可以被对角元绝对值的最大值控制住。所以我们的目标就是证明 $M_X^\theta-M_X^{\theta',l}$ 对角元的绝对值不会很大。

首先有：

$\lambda'-\bar{\lambda}=2\sqrt{d-1}(\cosh(\theta')-\cosh(\theta))=2d^{1-1/(2\epsilon)} \\ \lambda' / \bar{\lambda} = 1 + O(d^{1 / 2 - 1 / (2 \epsilon)}) = 1 + O(\epsilon)$

可得：$\cosh(\theta')-\cosh(\theta)=O(d^{1/2-1/(2\epsilon)})=O(\epsilon^2)$ 与 $\lambda' = \bar{\lambda} (1 + O(\epsilon))$。

于是由不等式 $\forall x\ge y\ge 0,(x-y)^2\le 2(\cosh(x)-\cosh(y))$（这一结论容易使用 Taylor 展开证明，这里略去不证），可以得到 $\theta'-\theta=O(\epsilon)$。

再来又有（这一结论证明较为简单，略去）：

$\dfrac l{l+1}\exp(-\theta')\le \dfrac{\sinh(l\theta')}{\sinh((l+1)\theta')}\le \exp(-\theta')$

于是：

$\dfrac{\sinh(l\theta')}{\sinh((l+1)\theta')}=\exp(-\theta')(1+O(1/l))=\exp(-\theta)(1+O(\epsilon))$

将上式代入到 $M_X^\theta-M_X^{\theta',l}$ 的表达式中可以发现其对角元都是 $O(\sqrt{d-1}\epsilon)$ 级别的。故：

$\lambda_1(M_X^l)\le \lambda_1(M_X^{\theta',l})+O(\sqrt{d-1}\epsilon)\le \lambda'+O(\bar{\lambda}\epsilon)=\bar{\lambda}(1+O(\epsilon))$

得证。$\Box$

Remark：观察如上证明过程可以发现：将 Main Lemma 中的 $\lambda_2(G)$ 替换成任意一个常数 $\lambda^*$ 都是可以的，只要这个常数 $\lambda^*$ 满足如下条件：对于任何顶点集的子集 $X$ 都有：

$\lambda_1(X)\le \lambda^*+\dfrac{cd|X|}{|V|}$

对于某个固定的常数 $c$。

主要定理：较为困难的下界——d/2

这篇文章的主要定理如下：

Main Thm：设 $G=(V,E)$ 是一个 $d$ 正则图，令 $\bar{\lambda}=\max\{\lambda_2(G),2\sqrt{d-1}\}:=2\sqrt{d-1}\cosh(\theta)\,(\theta\ge0)$，则对于顶点集的任意大小最多为 $d^{-1/\epsilon}|V|$ 子集 $X$，我们有：

$\dfrac{|N(X)|}{|X|} \ge \dfrac d2 \left( 1-\sqrt{1-\dfrac{4d-4}{\bar{\lambda}^2}} \right)(1-O(\epsilon))$

Idea：该定理证明思路如下：

• 设计⼀个与 $X,N(X)$ 相关的向量 $f$，而 $\langle Mf,f\rangle$ 被 $\lambda_1(M)$ 控制。
• 为了将 $N(X)$ 与 $X$ 分开（两者可能有交集），设计了 cover graph 方便计算。

Defn（Cover Graph）：设 $G=(V,E)$ 是一张图，则 $G$ 的 cover graph $G'$ 定义如下：顶点集为 $V'=V\times \{0,1\}$，而对于任意两点 $(u,x),(v,y)\in V'$，其之间有连边当且仅当 $x\ne y$ 且 $uv\in E$。

对于 $V'$ 的任意一个子集 $W$，令 $W_p=\{u\mid (u,0\text{ or }1)\in W\},W^*=W_p\times \{0,1\}$。

Fact：对于一张图 $G$，关于其 cover graph 有如下事实：

• 若 $G$ 是 $d$ 正则的，则 $G'$ 也是 $d$ 正则的；
• $G'$ 的特征值为 $G$ 的特征值再并上 $G$ 的特征值取反。进而 $\lambda_1(G)=\lambda_1(G')$，但注意并没有 $\lambda_2(G)=\lambda_2(G')$。

Proof of Main Thm：设 $G'$ 是 $G$ 的 cover graph，对于 $V'$ 的任意一个子集 $W$，有：

$\lambda_1(W)\le \lambda_1(W^*)=\lambda_1(W_p)\le \lambda_2(G)+d\dfrac{|W_p|}{n}=\lambda_2(G)+2d\dfrac{|W_p|}{|V'|}$

其中第一个等号是由上面的 Fact 来的。

对照上一节中的 Remark 即可发现 $\lambda_2(G)$ 是满足条件的 $\lambda^*$，故 Main Lemma 可以照常使用。

设 $X$ 是 $G$ 顶点集 $V$ 的一个大小为 $d^{-1/\epsilon}|V|$ 的子集。令 $Y=X\times \{0\}$ 为 $G'$ 顶点集 $V'$ 的子集。

令 $f=d\bm{1}_Y+\bar{\lambda}\bm{1}_{N'(Y)}$，$S=Y\cup N'(Y)$，配上 Main Lemma 即可得：

$\langle M_S^\theta f,f\rangle\le \bar{\lambda}(1+O(\epsilon))\|f\|_2^2$

而左边这一项根据 $M_X^\theta$ 定义，它是由两部分组成的，第一部分就是 $\langle A'_S f,f\rangle=2\bar{\lambda}d^2|Y|$。而第二部分是 $dI-\Delta_S$ 带来的：对于 $v\in Y$，$d-d_S(v)=0$；而对于所有的 $v\in N'(Y)$，我们把它加起来，则就是 $N'(Y)$ 所有跑出去的边数剪掉 $N'(Y)$ 在 $G'[S]$ 中的边数，即为：$d(|N'(Y)|-|Y|)$，所以第二项为 $\dfrac{1}{\sqrt{d-1}\exp(\theta)}d(|N'(Y)|-|Y|)\bar{\lambda}^2$。

再把 $f$ 表达式代入，则式子变为：

$2\bar{\lambda}d^2|Y|+\dfrac{1}{\sqrt{d-1}\exp(\theta)}d(|N'(Y)|-|Y|)\bar{\lambda}^2 \le \bar{\lambda}(1+O(\epsilon))(d^2|Y|+\bar{\lambda}^2|N'(Y)|)$

又因为 $|Y|=|X|,|N'(Y)|=|N(X)|$，且 $\dfrac{\bar{\lambda}}{\sqrt{d-1}\exp(\theta)}=\dfrac{2\cosh(\theta)}{\exp(\theta)}$，代入化简后可以得到：

$d|X|\left(d-\dfrac{2\cosh(\theta)}{\exp(\theta)} \right)\le |N(X)|\left(\bar{\lambda}^2-\dfrac{2d\cosh(\theta)}{\exp(\theta)} \right)(1+O(\epsilon))$

而：$\bar{\lambda}^2-\dfrac{2d\cosh(\theta)}{\exp(\theta)}=2\cosh(\theta)(d\exp(\theta) -2\cosh(\theta))$，故：

$\dfrac{|N(X)|}{|X|}\ge \dfrac{d}{2\exp(\theta) \cosh(\theta)}(1-O(\epsilon))$

$=\dfrac{d}{2}\left( 1-\sqrt{1-\dfrac{1}{\cosh^2 (\theta)}} \right)(1-O(\epsilon))=\dfrac d2 \left( 1-\sqrt{1-\dfrac{4d-4}{\bar{\lambda}^2}} \right)(1-O(\epsilon))$

得证。$\Box$

这样我们就证明了这一主要定理。因为 $\bar{\lambda}=2\sqrt{d-1}+o(1)$，所以 $\sqrt{1-\dfrac{4d-4}{\bar{\lambda}^2}}$ 是趋于 $0$ 的，所以 vertex expansion 就是 $\dfrac d2$ 的。

vertex expansion 为 d/2 的 Ramanujan 图的构造

这篇论文还给出了一组 vertex expansion 为 $\dfrac d2$ 的 Ramanujan 图的构造。

（先鸽子）

对于更小子集的 vertex expansion

值得一提的还有 MM21 第五节中的结果：

Thm（更小子集的 vertex expansion）：设 $G$ 是一个 $d$ 正则的 $n$ 顶点图，且其围长 $g(G)$ 大等于 $2\alpha \ln_{d-1}n+4$。则对于任意大小为 $n^\kappa$ 的顶点集合的子集 $S$，有：

$\dfrac{|\partial S|}{|S|}\ge d-\lambda_2(G)-\dfrac{d^{\kappa/\alpha}}2-\dfrac{d}{n^{1-\kappa}}$

其中 $\partial S=N(S)-S$。

Proof：设 $S$ 是一个大小为 $n^\kappa$ 的顶点集合的子集。设 $n_i$ 为 $\partial S$ 中满足 $e(v,S)=i$ 的 $v$ 的个数，则 $e(S,\partial S)=n_1+2n_2+\cdots+dn_d=d|S|-e(S,S)$。

构造一个新图，叫做 $H(S)$。其点集为 $S$，而边集在 $E(G[S])$ 的基础上，对于每个在 $\partial S$ 中的点 $v$，在 $S\cap N(v)$ 的内部随意加一课生成树（可以有重边）。

则 $|E(H(S))|=e(S,S)+n_2+2n_3+\cdots+(d-1)n_d=e(S,S)+e(S,\partial S)-|\partial S|=d|S|-e(S,S)-|\partial S|$，且 $g(H(S))\ge \dfrac 12g(G)\ge \alpha \ln_{d-1}n+2$。

又由 Expander Mixing Lemma 可得：

$\left|e(S,S)-\dfrac dn|S|^2 \right|\le \lambda_2(G)|S|\Longrightarrow e(S,S)\le \left(\lambda_2(G)+\dfrac{d|S|}n \right)|S|$

故：

$|E(H(S))|\ge \left(d-\lambda_2(G)-\dfrac{d|S|}n \right)|S|-|\partial S|$

这意味着 $H(S)$ 的平均度数至少为：

$2\left(d-\lambda_2(G)-\dfrac{d}n-\dfrac{|\partial S|}{|S|} \right)$

于是由 Moore Bound $(g(G)\le 2\ln_{\bar{d}-1}n+2)$ 可得：

$g(H(S))\le \dfrac{2\ln n^\kappa}{\ln\left(2\left(d-\lambda_2(G)-\dfrac{d}n-\dfrac{|\partial S|}{|S|} \right)-1 \right)}+2$

将 $g(H(S))$ 相关的不等式代入再整理即可的：

$\dfrac{|\partial S|}{|S|}\ge d-\lambda_2(G)-\dfrac{d^{\kappa/\alpha}}2-\dfrac{d}{n^{1-\kappa}}$

故得证。$\Box$

如果 $G$ 是一个 $d$ 正则 $n$ 顶点的 Ramanujan graph，则 $g(G)=\dfrac 43 \ln_{d-1} n+o_d(1)$（这是 Ramanujan graph 的性质，详见 LS19）。那么如果 $\kappa<1/3$ 则：

$\dfrac{|\partial S|}{|S|}\ge d(1-o_d(1))$

这个定理说明，对于亚线性大小的子集 $S$，其 vertex expansion 可以进一步增大到 $d$。而之前的定理则是对线性大小的子集进行的论述，两者适用范围不同。

参考文献

[1] Better Expansion for Ramanujan Grdphs. Nabil Kahale, 1991.

[2] High-girth Near-Ramanujan Graphs with Lossy Vertex Expansion. Theo McKenzie, Sidhanth Mohanty, 2021.

[3] 周翟恩和同学 2023.12.13 组会发言稿.

[4] A randomized construction of high girth regular graphs. Nati Linial, Michael Simkin, 2019.