Ramanujanグラフ
概要
Ramanujanグラフ（Ramanujan graph）とは、連結な $d$-正則グラフで、隣接行列の固有値のうち $d$ 以外のものの絶対値がすべて $2\sqrt{d-1}$ 以下であるものである。二部グラフでは $\pm d$ 以外の固有値に同じ条件を課し、二部 Ramanujan グラフという。Alon–Boppana の限界により $2\sqrt{d-1}$ は次数を固定して頂点を増やすときの最良の値で、$d\ge3$ の Ramanujan グラフはエクスパンダーで、直径は頂点の個数の対数程度である。$d-1$ が素数冪のとき Lubotzky–Phillips–Sarnak・Margulis・Morgenstern が無限列を構成し、二部の場合は Marcus–Spielman–Srivastava がすべての $d\ge3$ について存在を示した。
前提知識: 正則グラフ, 隣接行列, 二部グラフ, エクスパンダーグラフ
Ramanujan グラフ（Ramanujan graph）とは、連結な $d$-正則グラフで、隣接行列の固有値のうち $d$ 以外のものの絶対値がすべて $2\sqrt{d-1}$ 以下であるもののことである。二部グラフでは $\pm d$ を除いた固有値（自明でない固有値）に同じ条件を課し、二部 Ramanujan グラフ という。
次数 $d$ を固定して頂点を増やすとき、2 番目の固有値は $2\sqrt{d-1}$ より本質的に小さくはなれない（Alon–Boppanaの限界）。Ramanujan グラフはこの限界までスペクトルギャップを広げたグラフで、その意味で最良の エクスパンダーグラフ である。小さい例はすぐ確かめられるが、次数を固定して頂点の個数が限りなく増える列を作るのは難しく、Lubotzky–Phillips–Sarnak と Margulis は Ramanujan 予想の解決を使ってそれを構成した。名前はこれに由来する。二部グラフの場合は、Marcus–Spielman–Srivastava がすべての $d\ge3$ について無限列の存在を示した。
この記事では、例の判定、二部二重被覆、エクスパンダーとしての性質（スペクトルギャップ・辺の分布・直径）を証明し、無限列の構成は主張と所在を述べる。二部の場合は、2-lift による帰着の部分を証明する。
定義
この記事では、グラフは有限の単純グラフ（ループも多重辺もない）とする。頂点が $n$ 個の $d$-正則グラフ $G$ の隣接行列 $A$ の固有値を $d=\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$ と並べる（隣接行列 の定理「最大固有値と次数」により、すべての固有値の絶対値は $d$ 以下である）。$G$ が連結なら次が成り立つ。
- 固有値 $d$ の重複度は $1$ である（同じ定理の 3。重複度は連結成分の個数）。
- $-d$ が固有値であることと $G$ が二部グラフであることは同値で（隣接行列 の定理「スペクトルによる二部グラフの判定」の 1）、二部グラフのスペクトルは $0$ について対称なので、そのとき $-d$ の重複度も $1$ である。
連結な $d$-正則グラフの固有値 $d$ と、二部グラフの場合の $-d$ を 自明な固有値、それ以外を 自明でない固有値 という。
連結な $d$-正則グラフで、$d$ 以外のすべての固有値 $\theta$ が $\lvert\theta\rvert\le2\sqrt{d-1}$ をみたすものを Ramanujan グラフ という。
連結な $d$-正則二部グラフで、$\pm d$ 以外のすべての固有値 $\theta$ が $\lvert\theta\rvert\le2\sqrt{d-1}$ をみたすものを 二部 Ramanujan グラフ という。
$d\ge3$ なら $d>2\sqrt{d-1}$ なので、二部グラフは固有値 $-d$ をもつため def-rg-main の意味の Ramanujan グラフにはならない。したがって 2 つの定義は重ならず、どちらも「自明でない固有値の絶対値がすべて $2\sqrt{d-1}$ 以下」と言える。MSS14 §2.1（p. 2）は Lubotzky–Phillips–Sarnak に従ってこの合わせた形で定義し、二部のものも Ramanujan グラフと呼ぶ。def-rg-main は BH11 §4.1（p. 67）と エクスパンダーグラフ の定義「Ramanujan グラフの固有値の条件」に、def-rg-bipartite は Zha23 Definition 3.6.12（p. 127）にあたる。スペクトルの対称性から、def-rg-bipartite の条件は $\lambda_2\le2\sqrt{d-1}$ と同じである。$d=2$ の連結グラフは閉路 $C_n$ で、固有値 $2\cos(2\pi j/n)$ の絶対値はすべて $2$ 以下なので、条件は自動的にみたされる。意味のあるのは $d\ge3$ の場合である。
小さい例
| グラフ | $d$ | 自明でない固有値 | その絶対値の最大 | $2\sqrt{d-1}$ | 判定 |
|---|---|---|---|---|---|
| 完全グラフ $K_n$（$n\ge3$） | $n-1$ | $-1$ | $1$ | $2\sqrt{n-2}$ | Ramanujan |
| Petersen グラフ | $3$ | $1,\ -2$ | $2$ | $2\sqrt2\approx2.83$ | Ramanujan |
| 完全二部グラフ $K_{d,d}$（$d\ge2$） | $d$ | $0$ | $0$ | $2\sqrt{d-1}$ | 二部 Ramanujan |
| Heawood グラフ | $3$ | $\pm\sqrt2$ | $\sqrt2$ | $2\sqrt2$ | 二部 Ramanujan |
| 超立方体 $Q_m$（$m\ge2$） | $m$ | $m-2i$（$1\le i\le m-1$） | $m-2$ | $2\sqrt{m-1}$ | $m\le6$ のときに限り二部 Ramanujan |
$K_n$ の固有値は $n-1$ と $-1$（隣接行列 の例「完全グラフと完全二部グラフ」）、Petersen グラフの固有値は $3,1,-2$（Petersenグラフ、隣接行列 の例「Petersen グラフの隣接行列」）、$K_{d,d}$ の固有値は $\pm d$ と $0$ である（同じ例）。Heawood グラフは prop-rg-projective の $q=2$ の場合である。$Q_m$ の固有値は $m-2i$（$0\le i\le m$）である（BH11 §1.4.6、p. 10）。
超立方体の判定を開く
$Q_m$ の頂点 $x\in\{0,1\}^m$ と部分集合 $I\subset\{1,\dots,m\}$ について $\chi_I(x):=(-1)^{\sum_{j\in I}x_j}$ とおく。$x$ の隣接頂点は $x$ の第 $j$ 成分を変えた $x^{(j)}$ で、$\chi_I(x^{(j)})$ は $j\in I$ なら $-\chi_I(x)$、そうでなければ $\chi_I(x)$ なので、$\sum_j\chi_I(x^{(j)})=(m-2\lvert I\rvert)\chi_I(x)$ である。$2^m$ 個の $\chi_I$ は互いに直交するので、固有値は $m-2\lvert I\rvert$ である。$Q_m$ は連結な二部グラフで（二部グラフ の例「超立方体グラフの二部性」）、$m\ge2$ のとき自明でない固有値の絶対値の最大は $m-2$ である。$m-2\le2\sqrt{m-1}$ は $(m-2)^2\le4(m-1)$、すなわち $m^2-8m+8\le0$ と同値で、$4-2\sqrt2\le m\le4+2\sqrt2\approx6.83$ である。
強正則グラフ
強正則グラフ は $k$ のほかに固有値が 2 つしかないので、判定が簡単である。$\mathrm{srg}(v,k,\lambda,\mu)$ の制限された固有値（$\mathbf 1$ に直交する固有ベクトルをもつ固有値）を $r>s$ とすると、$r+s=\lambda-\mu$、$rs=\mu-k$ である（強正則グラフ の定理「固有値と重複度」）。この節の $\lambda,\mu,r,s$ はこの意味で使う。
$\Gamma$ を連結で二部でない $\mathrm{srg}(v,k,\lambda,\mu)$ とする。$\Gamma$ が Ramanujan グラフであることと、$\max\{r,-s\}\le2\sqrt{k-1}$ であることは同値である。
$\Gamma$ は連結なので $k$ の重複度は $1$ で、$\mathbf 1$ に直交する固有ベクトルの固有値は $k$ と異なる。よって $k$ 以外の固有値は制限された固有値 $r,s$ に一致し、どちらも現れる（強正則グラフ の定理「固有値と重複度」）。$\mu\le k$ なので $rs=\mu-k\le0$ であり、$r>s$ と合わせて $r\ge0\ge s$ である。したがって $k$ 以外の固有値の絶対値の最大は $\max\{r,-s\}$ であり、主張は def-rg-main そのものである。$\square$
連結な二部の強正則グラフは $K_{a,a}$（$a\ge2$）に限り（異なる部集合の隣接しない 2 頂点は共通の隣接頂点をもたないので、そのような対があれば $\mu=0$ となって連結でない。強正則グラフ の命題「連結でない強正則グラフ」の 1）、$s=-k$ は自明な固有値になる。この場合は def-rg-bipartite で判定し、自明でない固有値は $0$ だけなので二部 Ramanujan グラフである。
Paley グラフ． $q\equiv1\pmod4$ を素数冪、$q\ge5$ とすると、Paley グラフ $P_q$（Paleyグラフ）はすべて Ramanujan グラフである（BH11 p. 68 も例に挙げる）。ただし次数 $\frac{q-1}2$ は $q$ とともに増える。
確認を開く
$P_q$ は $\frac{q-1}2$-正則で、それ以外の固有値は $\frac{-1\pm\sqrt q}2$ である（Paleyグラフ の定理「Paley グラフの固有値」）。$\frac{1+\sqrt q}2=\frac{q-1}2$ となるのは $q=4$ だけなので $-\frac{q-1}2$ は固有値でなく、$P_q$ は二部でない。$\mathrm{srg}(q,\frac{q-1}2,\frac{q-5}4,\frac{q-1}4)$ であり（強正則グラフ の命題「Paley グラフは強正則」）、隣接しない 2 頂点は共通の隣接頂点を $\frac{q-1}4\ge1$ 個もつので連結である。$\max\{r,-s\}=\frac{1+\sqrt q}2$ で、$8(q-3)-(1+\sqrt q)^2=7q-2\sqrt q-25$ は $q$ について増加し、$q=5$ で $10-2\sqrt5>0$ である。よって $\frac{1+\sqrt q}2\le2\sqrt{\frac{q-1}2-1}$ であり、prop-rg-srg から主張が従う。
格子グラフ． $m\ge3$ のとき、$m\times m$ の格子 $L_2(m)$（$\mathrm{srg}(m^2,2(m-1),m-2,2)$、強正則グラフ の例「小さい例」）が Ramanujan であるのは $3\le m\le10$ のときに限る。自然な族でも、次数が増えると Ramanujan でなくなることがある。
確認を開く
$r+s=m-4$、$rs=4-2m$ から $r=m-2$、$s=-2$ である。三角形を含むので二部でなく、$\mu=2>0$ なので連結である。prop-rg-srg により、Ramanujan であることは $\max\{m-2,2\}\le2\sqrt{2m-3}$ と同値である。$m=3$ では $2\le2\sqrt3$ で成り立つ。$m\ge4$ では $(m-2)^2\le4(2m-3)$、すなわち $m^2-12m+16\le0$ と同値で、$6-2\sqrt5\le m\le6+2\sqrt5\approx10.47$ である。
射影平面の接続グラフ
位数 $q$ の有限 射影平面 は、点と直線がどちらも $q^2+q+1$ 個で、各直線の上に $q+1$ 個の点、各点を通る $q+1$ 本の直線があり、異なる 2 点を通る直線と、異なる 2 直線の交点がただ 1 つずつある（射影平面 の定理「有限射影平面の位数」と公理）。点と直線を頂点とし、点が直線の上にあるときに結んだ二部グラフを 接続グラフ という。
位数 $q$ の有限射影平面の接続グラフは、頂点が $2(q^2+q+1)$ 個の連結な $(q+1)$-正則二部グラフで、固有値は $\pm(q+1)$（重複度 $1$ ずつ）と $\pm\sqrt q$（重複度 $q^2+q$ ずつ）である。とくに二部 Ramanujan グラフである。
要点：点と直線の接続行列 $M$ は $MM^{\mathsf T}=M^{\mathsf T}M=qI+J$ をみたすので、隣接行列の 2 乗の固有値は $(q+1)^2$ と $q$ だけである。
詳しい証明を開く
$N:=q^2+q+1$ とし、点 $P$ と直線 $\ell$ について $P$ が $\ell$ の上にあれば $1$、なければ $0$ を成分とする $N\times N$ 行列を $M$ とする。$MM^{\mathsf T}$ の $(P,P')$ 成分は $P$ と $P'$ の両方を通る直線の本数なので、対角成分は $q+1$、それ以外は $1$ であり、$MM^{\mathsf T}=qI+J$ である。同様に $M^{\mathsf T}M=qI+J$ である（2 直線の交点はただ 1 つ）。接続グラフの隣接行列は $A=\begin{pmatrix}0&M\\M^{\mathsf T}&0\end{pmatrix}$ で、$A^2=\begin{pmatrix}qI+J&0\\0&qI+J\end{pmatrix}$ である。$qI+J$ の固有値は $q+N=(q+1)^2$（重複度 $1$）と $q$（重複度 $N-1$）なので、$A^2$ の固有値は $(q+1)^2$ が 2 個、$q$ が $2(N-1)$ 個である。$A$ の固有値の 2 乗が $A^2$ の固有値なので、$A$ の固有値は $\pm(q+1)$ と $\pm\sqrt q$ のどれかであり、二部グラフなので $\theta$ と $-\theta$ の重複度は等しい（隣接行列 の命題「二部グラフのスペクトルは対称」）。よって $\pm(q+1)$ は 1 個ずつ、$\pm\sqrt q$ は $q^2+q$ 個ずつである。$q+1$ の重複度が $1$ なので連結である。$\sqrt q\le2\sqrt q=2\sqrt{(q+1)-1}$ である。$\square$
$q=2$ の Fano 平面（射影平面 の例「Fano 平面」、Fano平面 の例「点と直線の接続グラフ」）の接続グラフは、頂点 $14$ 個の $3$-正則グラフで、Heawood グラフ と呼ばれる。$\mathbb P^2(\mathbb F_q)$ は素数冪 $q$ ごとに位数 $q$ の射影平面なので、次数 $q+1$ の二部 Ramanujan グラフが得られるが、この族でも次数は $q$ とともに増える。
二部二重被覆
$G$ の 二部二重被覆 $G\times K_2$ とは、頂点を $(v,0),(v,1)$（$v$ は $G$ の頂点）とし、$G$ の各辺 $uv$ について $(u,0)$ と $(v,1)$、$(u,1)$ と $(v,0)$ を結んだグラフである（BH11 §1.4.7、p. 10）。
$G$ を頂点が $n$ 個の連結で二部でない $d$-正則グラフとする。$G\times K_2$ は連結な $d$-正則二部グラフで、そのスペクトルは $G$ の固有値 $\lambda_i$ と $-\lambda_i$（$i=1,\dots,n$）を合わせたものである。とくに $G$ が Ramanujan グラフなら、$G\times K_2$ は二部 Ramanujan グラフである。
要点：隣接行列 $\begin{pmatrix}0&A\\A&0\end{pmatrix}$ は $(x,x)$ と $(x,-x)$ を固有ベクトルにもつ。連結性は奇閉路を 1 周して歩道の長さの偶奇を変えることによる。
詳しい証明を開く
正則・二部：$(v,\varepsilon)$ の隣接頂点は、$v$ の隣接頂点 $u$ について $(u,1-\varepsilon)$ なので次数は $d$ であり、ループも多重辺もない。辺は $V\times\{0\}$ と $V\times\{1\}$ を結ぶので二部グラフである。
スペクトル：頂点を $V\times\{0\}$、$V\times\{1\}$ の順に並べると隣接行列は $\begin{pmatrix}0&A\\A&0\end{pmatrix}$ である。$Ax=\lambda x$ なら $(x,x)$ は固有値 $\lambda$、$(x,-x)$ は固有値 $-\lambda$ の固有ベクトルである。$A$ の固有ベクトルの基底 $x_1,\dots,x_n$ から作った $2n$ 個のベクトル $(x_i,x_i)$、$(x_i,-x_i)$ は線形独立なので、スペクトルは主張のとおりである。
連結：$G$ は二部でないので奇数の長さの閉路 $C$ をもつ（二部グラフ の定理「閉路の長さによる特徴付け」）。$G$ の歩道 $v_0v_1\cdots v_\ell$ は、$G\times K_2$ の歩道 $(v_0,0)(v_1,1)(v_2,0)\cdots(v_\ell,\ell\bmod2)$ を与える。$G$ の 2 頂点 $u,v$ について、$u$ から $v$ への歩道の途中で $C$ の頂点に寄り、$C$ を 1 周してから戻ると、長さの偶奇が逆の歩道になる。よって $(u,0)$ から $(v,0)$ にも $(v,1)$ にも行けて、$G\times K_2$ は連結である。
Ramanujan であること：$G$ は連結で二部でないので、$d$ の重複度は $1$ で $-d$ は固有値でない。よって $G\times K_2$ の固有値 $\pm d$ は $\lambda_1=d$ から 1 個ずつ現れ、残りは $\pm\lambda_i$（$i\ge2$）で、絶対値は $2\sqrt{d-1}$ 以下である。$\square$
Zha23 p. 127 はこの構成を注意し、二部 Ramanujan グラフの存在は Ramanujan グラフの存在より弱い主張であると述べている。$G$ が二部グラフなら $G\times K_2$ は $G$ の 2 つの写しの非交和で、連結でない（BH11 §1.4.7）。
エクスパンダーとしての性質
Ramanujan グラフは自明でない固有値が小さいので、エクスパンダーグラフ の固有値による結果をそのまま強い形で使える。頂点の集合 $S,T$ について、$e(S,T)$ を $x\in S$、$y\in T$ が隣接する順序対 $(x,y)$ の個数とし、$s:=\lvert S\rvert$、$t:=\lvert T\rvert$ とおく。$h(G)$ は Cheeger 定数である（Cheegerの不等式(グラフ)）。
$d\ge3$ とし、$G$ を頂点が $n$ 個の $d$-正則グラフとする。
- $G$ が Ramanujan グラフか二部 Ramanujan グラフなら、$d-\lambda_2\ge(\sqrt{d-1}-1)^2$ であり、$h(G)\ge\frac12(\sqrt{d-1}-1)^2$ である。
- $G$ が Ramanujan グラフなら、すべての $S,T\subset V$ について
$$ \Bigl\lvert e(S,T)-\frac{d\,st}n\Bigr\rvert\le2\sqrt{d-1}\,\sqrt{st\Bigl(1-\frac sn\Bigr)\Bigl(1-\frac tn\Bigr)} $$
である。 - $G$ が二部 Ramanujan グラフで部集合が $L,R$（$\lvert L\rvert=\lvert R\rvert=m$）なら、すべての $S\subset L$、$T\subset R$ について
$$ \Bigl\lvert e(S,T)-\frac{d\,st}m\Bigr\rvert\le2\sqrt{d-1}\,\sqrt{st\Bigl(1-\frac sm\Bigr)\Bigl(1-\frac tm\Bigr)} $$
である。
とくに、次数 $d\ge3$ を固定した Ramanujan グラフ（または二部 Ramanujan グラフ）の列で頂点の個数が $\infty$ に発散するものは、エクスパンダー族である。
1．$G$ は連結なので $d$ の重複度は $1$ で、$\lambda_2\neq d$ である。二部の場合も $-d$ は最小の固有値で重複度 $1$ なので、$n\ge3$ なら $\lambda_2\neq-d$ である（$d\ge3$ なので $n\ge2d\ge6$）。よって $\lambda_2$ は自明でない固有値で $\lambda_2\le2\sqrt{d-1}$、$d-\lambda_2\ge d-2\sqrt{d-1}=(\sqrt{d-1}-1)^2$ である。Cheegerの不等式(グラフ) の系「正則グラフの場合」の $h(G)\ge\frac12(d-\lambda_2)$ から後半を得る。
2．$\lambda_2,\dots,\lambda_n$ はどれも $d$ と異なるので絶対値が $2\sqrt{d-1}$ 以下であり、$\lambda(G):=\max_{i\ge2}\lvert\lambda_i\rvert\le2\sqrt{d-1}$ である。エクスパンダーグラフ の定理「エクスパンダー混合補題」に代入すればよい。
3．$\mathbf 1$ と、$L$ で $1$、$R$ で $-1$ のベクトル $\sigma$ は、それぞれ固有値 $d$、$-d$ の固有ベクトルである。スペクトル定理 により、$u_1:=\mathbf 1/\sqrt{2m}$、$u_n:=\sigma/\sqrt{2m}$ を含む固有ベクトルの正規直交基底 $u_1,\dots,u_n$（$Au_i=\lambda_iu_i$）がとれ、$2\le i\le n-1$ の $\lambda_i$ は自明でないので $\lvert\lambda_i\rvert\le2\sqrt{d-1}$ である。$\mathbf 1_S=\sum_i\alpha_iu_i$、$\mathbf 1_T=\sum_i\beta_iu_i$ と展開すると、$S\subset L$、$T\subset R$ から $\alpha_1=\alpha_n=s/\sqrt{2m}$、$\beta_1=t/\sqrt{2m}$、$\beta_n=-t/\sqrt{2m}$ であり、
$$
e(S,T)=\mathbf 1_S^{\mathsf T}A\mathbf 1_T=d\alpha_1\beta_1-d\alpha_n\beta_n+\sum_{i=2}^{n-1}\lambda_i\alpha_i\beta_i=\frac{d\,st}m+\sum_{i=2}^{n-1}\lambda_i\alpha_i\beta_i
$$
である。$\sum_{i=2}^{n-1}\alpha_i^2=s-2\cdot\frac{s^2}{2m}=s\bigl(1-\frac sm\bigr)$、同様に $\sum_{i=2}^{n-1}\beta_i^2=t\bigl(1-\frac tm\bigr)$ なので、Cauchy–Schwarzの不等式 により主張を得る。
最後の主張は、1 により Cheeger 定数が $\frac12(\sqrt{d-1}-1)^2>0$ で一様に下から抑えられることと、エクスパンダー族の定義（エクスパンダーグラフ の定義「Cheeger 定数とエクスパンダー族」）による。$\square$
2 から、Ramanujan グラフの独立集合の大きさは $2\sqrt{d-1}\,n/(d+2\sqrt{d-1})$ 以下であることも従う（エクスパンダーグラフ の系「独立数と彩色数の評価」に $\lambda\le2\sqrt{d-1}$ を入れる）。3 は Zha23 Theorem 3.2.9（p. 105。証明は同書の演習 3.2.10）の二部の混合補題を、因子 $(1-s/m)(1-t/m)$ の分だけ強めて二部 Ramanujan グラフに当てはめた形である。
$G$ を頂点が $n\ge2$ 個の連結な $d$-正則グラフとし、$\lambda:=\max_{2\le i\le n}\lvert\lambda_i\rvert$ とおく。整数 $k\ge1$ が $d^k>(n-1)\lambda^k$ をみたせば、$G$ のどの 2 頂点 $u,v$（$u=v$ も含む）の間にも長さがちょうど $k$ の歩道がある。とくに、$d\ge3$ の Ramanujan グラフの直径は
$$
\Bigl\lfloor\frac{\log(n-1)}{\log\bigl(d/(2\sqrt{d-1})\bigr)}\Bigr\rfloor+1
$$
以下である。
$u_1=\mathbf 1/\sqrt n$ から始まる固有ベクトルの正規直交基底 $u_1,\dots,u_n$ をとる（スペクトル定理）。$u_i$ を列に並べた行列は直交行列なので、その行も正規直交であり、各頂点 $w$ について $\sum_iu_i(w)^2=1$ である。$A^k=\sum_i\lambda_i^ku_iu_i^{\mathsf T}$ なので
$$
(A^k)_{uv}=\frac{d^k}n+\sum_{i\ge2}\lambda_i^ku_i(u)u_i(v)
$$
であり、Cauchy–Schwarzの不等式 により第 2 項の絶対値は $\lambda^k\bigl(\sum_{i\ge2}u_i(u)^2\bigr)^{1/2}\bigl(\sum_{i\ge2}u_i(v)^2\bigr)^{1/2}=\lambda^k\bigl(1-\frac1n\bigr)$ 以下である。よって $(A^k)_{uv}\ge\frac1n\bigl(d^k-(n-1)\lambda^k\bigr)>0$ であり、隣接行列 の定理「隣接行列の冪と歩道の数」により長さ $k$ の歩道がある。
Ramanujan グラフでは $\lambda\le\rho:=2\sqrt{d-1}$ で、$d\ge3$ なら $d/\rho>1$ である。$k$ を上の式の値とすると $k>\log(n-1)/\log(d/\rho)$、すなわち $(d/\rho)^k>n-1$ なので $d^k>(n-1)\rho^k\ge(n-1)\lambda^k$ であり、どの 2 頂点も長さ $k$ の歩道、したがって長さ $k$ 以下の道で結ばれる。$\square$
$d$ を固定すれば直径は $O(\log n)$ であり、エクスパンダーグラフ の命題「エクスパンダーの直径」と同じ大きさである。$d/(2\sqrt{d-1})$ は $d=3$ では $3/(2\sqrt2)\approx1.06$ と $1$ に近いので、小さい $d$ では上界の定数は大きい。たとえば Petersen グラフでは実際の $\lambda=2$ を使えば $(3/2)^k>9$ となる $k=6$ が上界で、実際の直径は $2$ である。二部グラフでは $\lambda=d$ なので、この定理は当てはまらない（反例の表の 2 行目）。
無限列の構成
次数を固定して頂点の個数が限りなく増える Ramanujan グラフの列を作ることが中心の問題である。この節の定理はこの記事では証明しない。
$d-1$ が素数冪なら、$d$-正則 Ramanujan グラフで頂点の個数がいくらでも大きいものが存在する。
この主張は Zha23 Theorem 3.6.10（p. 127）と HLW06 Theorem 5.12（p. 489）にある。BH11 §4.1（p. 68）によれば、Lubotzky–Phillips–Sarnak と Margulis は、$4$ で割って $1$ 余る素数 $p$ ごとに次数 $p+1$ の Ramanujan グラフの無限列を構成し、HLW06 p. 488 によれば Morgenstern が $d-1$ が素数冪の場合に広げた。
Lubotzky–Phillips–Sarnak のグラフ $X^{p,q}$ は、$p,q$ を $4$ で割って $1$ 余る相異なる素数とし、射影一般線形群 $\mathrm{PGL}(2,q)$ の $p+1$ 個の元についての Cayleyグラフ の連結成分として作られる（HLW06 p. 489）。
構成を開く
$i^2\equiv-1\pmod q$ となる整数 $i$ を 1 つ固定する。$a_0^2+a_1^2+a_2^2+a_3^2=p$ の整数解で $a_0>0$ が奇数、$a_1,a_2,a_3$ が偶数のものはちょうど $p+1$ 個あり（Jacobi の定理）、各解から行列 $\begin{pmatrix}a_0+ia_1&a_2+ia_3\\-a_2+ia_3&a_0-ia_1\end{pmatrix}$ を作る。これらの $p+1$ 個の元の集合 $S$ は $\mathrm{PGL}(2,q)$ の中で逆元をとる操作で閉じており、Cayley グラフ $C(\mathrm{PGL}(2,q),S)$ の単位元を含む連結成分が $X^{p,q}$ である。$X^{p,q}$ は $(p+1)$-正則で、頂点の個数は $q^3$ の定数倍程度である（以上は HLW06 p. 489 の記述による）。
固有値の評価の証明には、数論の深い結果、すなわち Ramanujan 予想の解決が使われ、名前はそれに由来する（Zha23 p. 126）。HLW06 p. 524 によれば、最良の固有値の評価は、有限体上の多様体についての Ramanujan 予想を解いた Deligne の結果（Weil予想）とその後の評価に基づく。もとの Ramanujan 予想は、保型形式 の Fourier 係数の大きさについての予想である。
$d-1$ が素数冪でない $d$（最小は $d=7$）について、$d$-正則 Ramanujan グラフの無限列があるかは、Zha23 p. 126 の時点で未解決である。一方 Zha23 Theorem 3.6.7（p. 126）によれば、Friedman は、$d$ と $\varepsilon>0$ を固定すると、頂点の多い無作為な $d$-正則グラフは確率が $1$ に近いという意味で $\lambda_2,\dots,\lambda_n$ の絶対値がすべて $2\sqrt{d-1}+\varepsilon$ 以下であることを示した。Alon–Boppanaの限界 と合わせると、定数 $2\sqrt{d-1}$ はちょうど最良である。
二部 Ramanujan グラフの存在
二部の場合は、すべての次数について存在が分かっている。
すべての $d\ge3$ について、$d$-正則二部 Ramanujan グラフで頂点の個数がいくらでも大きいものが存在する。
この定理は MSS14 Theorem 5.5（p. 9）であり、Zha23 Theorem 3.6.13（p. 127）にもある。証明は 2-lift という操作で頂点の個数を 2 倍にしていく。この記事では、証明の核心の定理（thm-rg-signing）を引用し、そこから thm-rg-mss を導く部分を証明する。
グラフ $G=(V,E)$ の辺に符号 $\varsigma:E\to\{\pm1\}$ を付けたものを 符号付け といい、隣接行列の辺 $uv$ に対応する成分 $1$ を $\varsigma(uv)$ に替えた行列 $A_\varsigma$ を 符号付き隣接行列 という。$\varsigma$ に対し、頂点 $(v,0),(v,1)$（$v\in V$）をもち、$\varsigma(uv)=1$ なら $(u,0)(v,0)$ と $(u,1)(v,1)$、$\varsigma(uv)=-1$ なら $(u,0)(v,1)$ と $(u,1)(v,0)$ を結んだグラフを $G$ の 2-lift という（MSS14 §2.2、pp. 2–3）。すべての符号が $-1$ なら、2-lift は二部二重被覆 $G\times K_2$ である。
$G$ を $d$-正則グラフ、$\varsigma$ を符号付け、$\hat G$ を対応する 2-lift とする。
- $\hat G$ は $d$-正則グラフで、$G$ が二部グラフなら $\hat G$ も二部グラフである。
- $\hat G$ のスペクトルは、$A$ のスペクトルと $A_\varsigma$ のスペクトルを（重複度をこめて）合わせたものである。
- $d\ge3$ とする。$G$ が二部 Ramanujan グラフで、$A_\varsigma$ の固有値がすべて $2\sqrt{d-1}$ 以下なら、$\hat G$ は頂点が $G$ の 2 倍の二部 Ramanujan グラフである。
要点：符号 $+1$ の辺の隣接行列を $A_+$、$-1$ の辺のものを $A_-$ とすると、2-lift の隣接行列 $\begin{pmatrix}A_+&A_-\\A_-&A_+\end{pmatrix}$ は $(x,x)$ の形のベクトルの上で $A=A_++A_-$、$(y,-y)$ の形のベクトルの上で $A_\varsigma=A_+-A_-$ として働く。
詳しい証明を開く
1：$v$ の各辺 $uv$ は $(v,\varepsilon)$ にちょうど 1 本の辺を与えるので $\hat G$ は $d$-正則で、ループも多重辺もない。$G$ の部集合が $X,Y$ なら、$X\times\{0,1\}$ と $Y\times\{0,1\}$ が $\hat G$ の部集合になる。
2：符号 $+1$ の辺だけの隣接行列を $A_+$、$-1$ の辺だけのものを $A_-$ とすると $A=A_++A_-$、$A_\varsigma=A_+-A_-$ であり、$\hat G$ の隣接行列は $\begin{pmatrix}A_+&A_-\\A_-&A_+\end{pmatrix}$ である。$Ax=\theta x$ なら $(x,x)$ は固有値 $\theta$、$A_\varsigma y=\eta y$ なら $(y,-y)$ は固有値 $\eta$ の固有ベクトルである。$A$ と $A_\varsigma$ の固有ベクトルの基底から作った $2n$ 個のベクトルは線形独立なので、2 を得る。
3：$G$ は二部なので、隣接行列 の命題「二部グラフのスペクトルは対称」の証明と同じく、部集合ごとに $\pm1$ を並べた対角行列 $D$ について $DA_\varsigma D^{-1}=-A_\varsigma$ であり、$A_\varsigma$ のスペクトルも $0$ について対称である。よって $A_\varsigma$ の固有値はすべて区間 $[-2\sqrt{d-1},2\sqrt{d-1}]$ に入る。2 により $\hat G$ の固有値は、$G$ の固有値（$\pm d$ が 1 個ずつと、絶対値 $2\sqrt{d-1}$ 以下のもの）と、$A_\varsigma$ の固有値である。$d\ge3$ なので $2\sqrt{d-1}< d$ であり、$\hat G$ の固有値 $d$ の重複度は $1$ で、$\hat G$ は連結である（隣接行列 の定理「最大固有値と次数」の 3）。$\hat G$ は 1 により $d$-正則二部グラフで、$\pm d$ 以外の固有値の絶対値は $2\sqrt{d-1}$ 以下である。$\square$
2 は Bilu–Linial による（MSS14 §2.2、p. 3 は Bilu–Linial の論文の Lemma 3.1 として引いている）。Marcus–Spielman–Srivastava の核心は次の定理である。
すべての $d$-正則グラフ $G$ に、符号付き隣接行列 $A_\varsigma$ の固有値がすべて $2\sqrt{d-1}$ 以下になる符号付け $\varsigma$ がある。この記事では証明しない。
thm-rg-signing を認めて、thm-rg-mss を証明する。
$d\ge3$ とする。$K_{d,d}$ は二部 Ramanujan グラフである（ex-rg-small）。二部 Ramanujan グラフ $G$ に thm-rg-signing の符号付けをとると、prop-rg-lift の 3 により、頂点が 2 倍の二部 Ramanujan グラフが得られる。これを繰り返すと、頂点が $2d\cdot2^j$ 個（$j=0,1,2,\dots$）の $d$-正則二部 Ramanujan グラフが得られる。$\square$
MSS14 は Bilu–Linial の予想（符号付き隣接行列の固有値の絶対値をすべて $2\sqrt{d-1}$ 以下にできる）の弱い形として thm-rg-signing を示した。最小の固有値は制御できないので、スペクトルが対称な二部グラフの場合だけ結論が得られる（同 §2.2、p. 3）。
反例：条件を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 連結（def-rg-main の他の条件は残す） | Petersen グラフ 2 つの非交和 | $d=3$ と異なる固有値は $1,-2$ だけだが、$\lambda_2=3$ でスペクトルギャップは $0$、Cheeger 定数も $0$ |
| 二部でない（thm-rg-diameter） | $K_{d,d}$（$d\ge3$、二部 Ramanujan） | どの $k$ についても、長さ $k$ の歩道で結ばれない 2 頂点がある |
| 次数 $d$ を固定する（エクスパンダー族になること） | 完全グラフの列 $K_3,K_4,\dots$ | どれも Ramanujan グラフだが、次数が有界でないのでエクスパンダー族ではない |
各行の確認を開く
1 行目：Petersen グラフ 2 つの非交和は $3$-正則で、スペクトルは Petersen グラフの $3,1^{(5)},(-2)^{(4)}$ を 2 回合わせた $3^{(2)},1^{(10)},(-2)^{(8)}$ である。$3$ と異なる固有値の絶対値は $2\le2\sqrt2$ 以下だが、連結でないので固有値 $3$ が 2 重になり $\lambda_2=3$、1 つの成分 $S$（頂点 $10$ 個）は $\partial S=\emptyset$ なので $h=0$ である。外したのは連結性だけである。
2 行目：$K_{d,d}$ は連結な二部グラフで、自明でない固有値は $0$ だけなので二部 Ramanujan グラフである。同じ部集合の 2 頂点を結ぶ歩道の長さは偶数、異なる部集合の 2 頂点を結ぶ歩道の長さは奇数なので、どの $k$ についても長さ $k$ の歩道で結ばれない組がある。$\lambda=\max_{i\ge2}\lvert\lambda_i\rvert=d$ なので $d^k>(n-1)\lambda^k$ はみたされない。外したのは「二部でない」だけである。
3 行目：$K_n$（$n\ge3$）は ex-rg-small のとおり Ramanujan グラフである。エクスパンダー族は次数を固定した列なので、次数 $n-1$ が増える列は定義に当てはまらない。外したのは次数の固定だけである。
関連項目
- 前提: 正則グラフ, 隣接行列, 二部グラフ
- 限界: Alon–Boppanaの限界
- 例: Petersenグラフ, 強正則グラフ, Paleyグラフ, 射影平面
- 性質: エクスパンダーグラフ, Cheegerの不等式(グラフ)
- 分野: スペクトルグラフ理論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
