5. Ramanujan 图

定义 5.1. 一个 Ramanujan 图是如下的一个 $d$-正则图: 假设它的邻接矩阵的特征值是 $d={\lambda }_1\ge \cdots \ge {\lambda }_n$ , 那么它需要满足 $|{\lambda }_2|,|{\lambda }_n|\le 2\sqrt{d-1}$. 也就是说, 它是一个 $\lambda \le 2\sqrt{d-1}$ 的 $(n,d,\lambda )$-图.

一个 Ramanujan 图的例子是 $K_{d+1}$, 因为 ${\lambda }_2=\cdots ={\lambda }_n=-1$. 但是我们更感兴趣的情况是, 固定 $d$ 而让 $n$ 趋于无穷的情况. 对于一个固定的 $d$, 是否存在无限多个 $d$-正则的 Ramanujan 图呢?

猜想 5.2. 对于所以的 $d\ge 3$, 都存在无限多个 $d$-正则的 Ramanujan 图.

我们会讨论关于这个猜想的一些部分结果.

定理 5.3 (Lubotzky-Phillips-Sarnak, Margulis). 以上猜想对所有 $d-1$ 是质数的 $d$ 成立.

定理 5.3 的证明方法是显示地构造群 $PSL(2,q)$ 的 Cayley 图, 它用到了数论中关于 Ramanujan 的一些猜想的深刻结论 (Ramanujan 图的名字是这么来的) . 1944 年, Morgenstern 加强了定理 5.3 的结论, 证明到了所有的 $d-1$ 是质数的幂的 $d$. 这基本上就是现在我们所知道的全部, 特别的, 猜想 5.2 对 $d=7$ 是否成立都还是未知的.

一个有趣的问题是: 考虑随机图中, 除了 ${\lambda }_1$ 以外, 最大的特征值如何分布呢?

定理 5.4 (Friedman). 固定 $d\ge 3$. 一个随机的 $n$ 个点的 $d$-正则图, 以 $1-o(1)$ 的概率, 几乎是一个 Ramanujan 图, 具体来说

$$\max \{|{\lambda }_2|,|{\lambda }_n|\}\le 2\sqrt{d-1}+o(1)$$

这里 $o(1)$ 项随着 $n\to \infty$ 而趋近于 $0$.

一些实验的结果显示, 似乎 $n$ 个点的图中固定比例 ($0$ 到 $1$ 之间) 的一部分 ($n\to \infty$) 应该是 Ramanujan 图. 但是, 在这条线上还没有严格的结论.

最近对于这个问题在二分图的情况, 有一些重要进展:

注意对于所有的二分图, ${\lambda }_i=-{\lambda }_{n+1-i}$. 这是因为, 如果令二分图的两个部分分别是 $A$ 和 $B$, 然后有一个特征值为 $\lambda$ 的特征向量, 它在 $A$ 的位置上等于 $v_A$, 在 $B$ 的位置上等于 $v_B$, 那么我们把 $v_B$ 取反, 就得到了一个特征值是 $-\lambda$ 的特征向量. 所以说一个二分图是二分 Ramanujan 图, 当且仅当 ${\lambda }_2\le 2\sqrt{d-1}$.

每一个 Ramanujan 图 $G$ 都有一个对应的二分 Ramanujan 图: 我们可以构造 $G\times K_2$; 如果 $G$ 有特征值 $\{{\lambda }_i\}$, 那么 $G\times K_2$ 就有特征值 $\{{\lambda }_i\}\cup \{-{\lambda }_i\}$, 所以 $d$-正则二分 Ramanujan 图问题是原问题的一个弱化.

定理 5.5 (Marcus-Spielman-Srivastava). 对于任意的 $d$, 都存在无穷多个 $d$-正则二分 Ramanujan 图.

定理 5.5 的证明用了一个特备聪明的随机图构造.