Alon–Boppanaの限界
概要
Alon–Boppanaの限界（Alon–Boppana bound）とは、次数 $d$ を固定したループのない $d$-正則グラフについて、隣接行列の 2 番目に大きい固有値 $\lambda_2$ が、頂点の個数 $n$ を限りなく増やすと $2\sqrt{d-1}-o(1)$ 以上になるという定理である。離れた 2 本の辺のまわりに試験関数を置いて Rayleigh 商を評価すると、直径 $D$ の連結グラフで誤差が $O(1/D)$ の下界が得られ、直径は頂点の個数の対数以上なので誤差は $O(1/\log n)$ になる。値 $2\sqrt{d-1}$ は無限の $d$-正則木のスペクトル半径で、連結で $d$ 以外の固有値がすべて絶対値 $2\sqrt{d-1}$ 以下のものが Ramanujan グラフである。
Alon–Boppana の限界（Alon–Boppana bound）とは、次数 $d$ を固定したループのない $d$-正則グラフについて、隣接行列の 2 番目に大きい固有値 $\lambda_2$ が、頂点の個数 $n$ を限りなく増やすと $2\sqrt{d-1}$ より本質的に小さくはなれないという定理である。式で書けば
$$
\lambda_2\ \ge\ 2\sqrt{d-1}-o(1)\qquad(n\to\infty)
$$
であり、$o(1)$ は $d$ だけによって決まる、$n\to\infty$ で $0$ に近づく量である。
$\lambda_2$ が次数 $d$ から離れているほど、グラフはよく「広がる」（エクスパンダーグラフ）。この定理は、次数を固定したままでは広がりの良さに越えられない上限があることを示す。値 $2\sqrt{d-1}$ は、すべての頂点の次数が $d$ の無限の木のスペクトル半径である。
この記事では、Nilli による試験関数の方法で、直径が大きいこと から $\lambda_2$ の下界を導く形を証明する。直径 $D$ の連結な $d$-正則グラフでは誤差は $O(1/D)$ であり、直径は頂点の個数の対数以上なので、誤差は $O(1/\log n)$ になる。
定義と記号
この記事では、グラフは有限で ループをもたない とし、多重辺は許す。隣接行列 $A$ の $(u,v)$ 成分は $u$ と $v$ を結ぶ辺の本数である。$A$ は実対称行列なので、固有値はすべて実数で、$\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$ と並べる。すべての成分が $1$ のベクトルを $\mathbf 1$ と書く。$d$-正則グラフでは $A\mathbf 1=d\mathbf 1$ で、$\lambda_1=d$ であり、すべての固有値の絶対値は $d$ 以下である（隣接行列 の定理「最大固有値と次数」。証明は多重辺があっても同じである）。
2 頂点 $u,v$ の距離 $\operatorname{dist}(u,v)$ は、$u$ と $v$ を結ぶ道の辺の本数の最小値である（結ぶ道がなければ $\infty$）。連結グラフの 2 頂点の距離の最大値を 直径 という（グラフの距離）。頂点の集合 $U$ と頂点 $v$ の距離を $\operatorname{dist}(v,U):=\min_{u\in U}\operatorname{dist}(v,u)$、2 本の辺 $e,e'$ の距離を、$e$ の端点と $e'$ の端点の距離の最小値と定める。
ベクトル $x\in\mathbb R^V$ について、辺の上の差の 2 乗の和を
$$
Q(x):=\sum_{uv\in E}(x_u-x_v)^2
$$
とおく（多重辺は本数だけ数える）。また $x^{\mathsf T}x=\sum_vx_v^2$ である。
$G$ を頂点が $n\ge2$ 個のループのない $d$-正則グラフとする。
- すべての $x\in\mathbb R^V$ について $x^{\mathsf T}Ax=d\,x^{\mathsf T}x-Q(x)$ である。
- $x\neq0$ が $\mathbf 1$ に直交すれば $\lambda_2\ge x^{\mathsf T}Ax/x^{\mathsf T}x=d-Q(x)/x^{\mathsf T}x$ である。
1：辺 $uv$ ごとに $(x_u-x_v)^2=x_u^2+x_v^2-2x_ux_v$ である。各頂点はちょうど $d$ 本の辺の端点なので（ループがないので、1 本の辺は 2 つの相異なる端点をもつ）、$x_u^2+x_v^2$ を辺について足すと $d\sum_vx_v^2$ になる。一方 $x^{\mathsf T}Ax=\sum_{u,v}A_{uv}x_ux_v$ は、各辺 $uv$ を $(u,v)$ と $(v,u)$ の 2 回数えるので $2\sum_{uv\in E}x_ux_v$ である。合わせて 1 を得る。
2：スペクトル定理 により、$u_1=\mathbf 1/\sqrt n$ から始まる $A$ の固有ベクトルの正規直交基底 $u_1,\dots,u_n$、$Au_i=\lambda_iu_i$ がとれる（$\lambda_1=d$。$d$ の重複度が $2$ 以上でも、固有空間の正規直交基底を $u_1$ から始めればよい）。$x\perp\mathbf 1$ なら $x=\sum_{i\ge2}c_iu_i$ と書けて、$x^{\mathsf T}Ax=\sum_{i\ge2}\lambda_ic_i^2\le\lambda_2\sum_{i\ge2}c_i^2=\lambda_2\,x^{\mathsf T}x$ である。1 と合わせて 2 を得る。$\square$
$dI-A$ は Laplacian行列 であり、1 は $x^{\mathsf T}(dI-A)x=Q(x)$ と同じことである。2 は、$\lambda_2$ が $\mathbf 1$ に直交するベクトルの上での Rayleigh商 の最大値であることの易しい半分である。したがって、$\lambda_2$ を下から抑えるには、$\mathbf 1$ に直交し、$Q(x)/x^{\mathsf T}x$ が小さい 試験関数（試しのベクトル）$x$ を 1 つ作ればよい。
主定理
$d\ge2$ とし、$G$ をループのない連結な $d$-正則グラフ、その直径を $D$ とする。$D\ge4$ なら
$$
\lambda_2\ \ge\ 2\sqrt{d-1}-\frac{2\sqrt{d-1}-1}{\lfloor D/2\rfloor-1}
$$
である。
証明は次の節で与える。直径が $D$ なら、距離が $D-2$ 以上離れた 2 本の辺がある。それぞれの辺のまわりに、辺からの距離が $1$ 増えるごとに値が $(d-1)^{-1/2}$ 倍になる試験関数を置き（lem-ab-test）、2 つの差をとって $\mathbf 1$ に直交させる（prop-ab-two-edges）。その Rayleigh 商を lem-ab-variational に代入すればよい。
右辺は $D$ が大きいほど $2\sqrt{d-1}$ に近い。直径は頂点の個数とともに大きくなるので、次の形が従う。
$d\ge2$ を固定する。
- ループのない $d$-正則グラフの列 $G_1,G_2,\dots$ で頂点の個数 $n_j$ が $\infty$ に発散するものについて、$\liminf_{j\to\infty}\lambda_2(G_j)\ge2\sqrt{d-1}$ である。すなわち $\lambda_2\ge2\sqrt{d-1}-o(1)$（$n\to\infty$）であり、$o(1)$ は $d$ だけによる。
- $d\ge3$ とし、$G$ を頂点が $n$ 個のループのない連結な $d$-正則グラフとする。$n>3(d-1)^3$ なら、$L:=\log_{d-1}(n/3)$ とおいて
$$ \lambda_2\ \ge\ 2\sqrt{d-1}-\frac{2\,(2\sqrt{d-1}-1)}{L-3} $$
である。
2 の誤差は、$n\ge9(d-1)^6$ なら $L-3\ge\log n/(2\log(d-1))$ なので $8\sqrt{d-1}\,\log(d-1)/\log n$ 以下であり、BH11 Proposition 4.1.1（p. 67）が $d\ge3$ について述べる誤差の大きさ $2\sqrt{d-1}\,\bigl(1-O(\log(d-1)/\log n)\bigr)$ と同じ形である。$d$ を固定しない場合については、後の反例の表の 1 行目を見よ。
証明
辺のまわりの試験関数
1 本の辺 $e=st$ を中心にして、そこから離れるにつれて $(d-1)^{-1/2}$ 倍ずつ小さくなる関数を考える。
$d\ge2$ とし、$G$ をループのない $d$-正則グラフ、$e=st$ をその辺、$k\ge0$ を整数とする。$i\ge0$ について $V_i:=\{v\mid\operatorname{dist}(v,\{s,t\})=i\}$ とおき（$V_0=\{s,t\}$）、
$$
f_v:=\begin{cases}(d-1)^{-i/2}&(v\in V_i,\ i\le k)\\ 0&(\operatorname{dist}(v,\{s,t\})>k)\end{cases}
$$
と定める。このとき
$$
Q(f)\ \le\ \Bigl(d-2\sqrt{d-1}+\frac{2\sqrt{d-1}-1}{k+1}\Bigr)f^{\mathsf T}f
$$
である。
$V_i$ と $V_j$ の間の辺の本数を $e(V_i,V_j)$ と書く。
辺の行き先． 辺 $uv$ の両端の $\{s,t\}$ からの距離の差は $1$ 以下なので（グラフの距離 の三角不等式）、辺は同じ $V_i$ の中にあるか、$V_i$ と $V_{i+1}$ を結ぶかのどちらかである。$i\ge1$ のとき、$V_i$ の各頂点は $V_{i-1}$ の頂点と結ぶ辺を少なくとも 1 本もつので、$V_{i+1}$ へ向かう辺は $d-1$ 本以下である。$i=0$ のとき、$s$ と $t$ はそれぞれ辺 $e$ の端点であり、$e$ は $V_0$ の中の辺なので、$V_1$ へ向かう辺はやはり $d-1$ 本以下である。よって
$$
e(V_i,V_{i+1})\le(d-1)\lvert V_i\rvert\qquad(i\ge0)
$$
である。さらに $V_{i+1}$ の各頂点は $V_i$ の頂点と辺で結ばれているので $\lvert V_{i+1}\rvert\le e(V_i,V_{i+1})\le(d-1)\lvert V_i\rvert$ であり、これを繰り返すと
$$
\frac{\lvert V_k\rvert}{(d-1)^k}\le\frac{\lvert V_i\rvert}{(d-1)^i}\qquad(0\le i\le k)
$$
である。
$Q(f)$ の計算． $f$ は各 $V_i$ の上で一定なので、同じ $V_i$ の中の辺は $Q(f)$ に寄与しない。$V_i$ と $V_{i+1}$（$i< k$）の間の辺は 1 本あたり
$$
\bigl((d-1)^{-i/2}-(d-1)^{-(i+1)/2}\bigr)^2=(d-1)^{-i}\bigl(1-(d-1)^{-1/2}\bigr)^2
$$
を寄与し、$V_k$ と $V_{k+1}$ の間の辺は 1 本あたり $(d-1)^{-k}$ を寄与する。それより遠い辺は寄与しない。$a_i:=\lvert V_i\rvert(d-1)^{-i}$ とおくと $f^{\mathsf T}f=\sum_{i=0}^ka_i$ であり、辺の本数の評価から
$$
Q(f)\le\sum_{i=0}^{k-1}(d-1)\bigl(1-(d-1)^{-1/2}\bigr)^2a_i+(d-1)a_k
$$
である。$(d-1)\bigl(1-(d-1)^{-1/2}\bigr)^2=(\sqrt{d-1}-1)^2=d-2\sqrt{d-1}$ であり、最後の項を $(d-1)a_k=(d-2\sqrt{d-1})a_k+(2\sqrt{d-1}-1)a_k$ と分けると
$$
Q(f)\le(d-2\sqrt{d-1})\sum_{i=0}^ka_i+(2\sqrt{d-1}-1)\,a_k
$$
である。$a_k\le a_i$（$0\le i\le k$）を $k+1$ 個足すと $(k+1)a_k\le f^{\mathsf T}f$ なので、$2\sqrt{d-1}-1>0$ と合わせて主張を得る。$\square$
この補題は Zha23 Lemma 3.6.4（pp. 122–123）で、証明もそれに従った。中心を頂点 $v$ 1 つにすると、$v$ から $V_1$ へ向かう辺は $d$ 本あり、1 段目だけ評価 $e(V_0,V_1)\le(d-1)\lvert V_0\rvert$ が成り立たない。辺を中心にとるのは、両端の頂点がお互いの隣接頂点を 1 つずつ使うので、どの段でも「外へ向かう辺は $d-1$ 本以下」がそろうためである（Zha23 Remark 3.6.5、p. 124 はこの点を問いとしている）。
離れた 2 本の辺
$f$ は $\mathbf 1$ に直交しない（成分がすべて $0$ 以上で、$V_0$ では正）。そこで、遠く離れた 2 本の辺のまわりの試験関数の差をとる。
$d\ge2$、$k\ge0$ とし、$G$ をループのない $d$-正則グラフとする。距離が $2k+2$ 以上の 2 本の辺（異なる連結成分にある辺でもよい）があれば
$$
\lambda_2\ \ge\ 2\sqrt{d-1}-\frac{2\sqrt{d-1}-1}{k+1}
$$
である。
2 本の辺を $e,e'$ とし、$e$ について lem-ab-test の $f$ を、$e'$ について同じ作り方の $g$ を作る。$c:=d-2\sqrt{d-1}+\frac{2\sqrt{d-1}-1}{k+1}$ とおくと $Q(f)\le c\,f^{\mathsf T}f$、$Q(g)\le c\,g^{\mathsf T}g$ である。
台が離れていること． $f_u\neq0$ なら $\operatorname{dist}(u,e)\le k$、$g_w\neq0$ なら $\operatorname{dist}(w,e')\le k$ である。このとき $\operatorname{dist}(e,e')\le k+\operatorname{dist}(u,w)+k$ なので $\operatorname{dist}(u,w)\ge2$ である。よって $f$ と $g$ の台（$0$ でない成分の頂点の集合）は交わらず、両者の台を結ぶ辺もない。
差をとる． $\mathbf 1^{\mathsf T}g>0$ なので、$\tau:=\mathbf 1^{\mathsf T}f/\mathbf 1^{\mathsf T}g$ とおき $h:=f-\tau g$ とすると $h\perp\mathbf 1$、$h\neq0$ である。台が交わらないので $h^{\mathsf T}h=f^{\mathsf T}f+\tau^2g^{\mathsf T}g$ である。また各辺 $uv$ は、$f$ の台と $g$ の台の両方には触れないので、$(h_u-h_v)^2$ は $(f_u-f_v)^2$ か $\tau^2(g_u-g_v)^2$ のどちらかに等しく、もう一方は $0$ である。よって $Q(h)=Q(f)+\tau^2Q(g)\le c\,h^{\mathsf T}h$ であり、lem-ab-variational の 2 により $\lambda_2\ge d-Q(h)/h^{\mathsf T}h\ge d-c$ である。$d-c$ は主張の右辺に等しい。$\square$
thm-ab-main を証明する。
直径 $D$ を実現する 2 頂点 $x,y$ をとり、$x$ を端点とする辺 $e$、$y$ を端点とする辺 $e'$ をとる（$d\ge1$ なので辺はある）。$e$ の端点は $x$ から距離 $1$ 以内、$e'$ の端点は $y$ から距離 $1$ 以内なので、$\operatorname{dist}(e,e')\ge D-2$ である。$k:=\lfloor D/2\rfloor-2$ とおくと、$D\ge4$ から $k\ge0$ であり、$2k+2=2\lfloor D/2\rfloor-2\le D-2$ である。prop-ab-two-edges を当てると、$k+1=\lfloor D/2\rfloor-1$ なので主張を得る。$\square$
直径は頂点の個数の対数以上
$d\ge2$ とし、$G$ を頂点が $n$ 個のループのない連結な $d$-正則グラフ、直径を $D$ とする。
$$
n\ \le\ 1+d\sum_{j=1}^{D}(d-1)^{j-1}
$$
である。とくに $d\ge3$ なら $n<3(d-1)^D$、すなわち $D>\log_{d-1}(n/3)$ である。
頂点 $v$ を 1 つ固定し、$v$ からの距離が $j$ の頂点の集合を $S_j$ とする。$G$ は連結で直径が $D$ なので、すべての頂点は $S_0,\dots,S_D$ のどれかに入る。$\lvert S_1\rvert\le d$ であり、$j\ge1$ のとき $S_j$ の各頂点は $S_{j-1}$ と結ぶ辺をもつので $S_{j+1}$ へ向かう辺は $d-1$ 本以下、よって $\lvert S_{j+1}\rvert\le(d-1)\lvert S_j\rvert$ である。したがって $\lvert S_j\rvert\le d(d-1)^{j-1}$（$j\ge1$）で、これを足して最初の不等式を得る。$d\ge3$ なら右辺は $1+\frac d{d-2}\bigl((d-1)^D-1\bigr)\le1+3\bigl((d-1)^D-1\bigr)<3(d-1)^D$ である（$\frac d{d-2}\le3$）。$\square$
cor-ab-vertices を証明する。
2．$G$ の直径を $D$ とすると、lem-ab-diameter により $D>L>3$ なので $D\ge4$ である。$\lfloor D/2\rfloor-1\ge\frac{D-1}2-1=\frac{D-3}2>\frac{L-3}2>0$ なので、thm-ab-main の誤差の項は $\frac{2(2\sqrt{d-1}-1)}{L-3}$ より小さい。
1．$G_j$ が連結でないとき、連結成分 $C$ を 1 つとり、$x:=\lvert V\setminus C\rvert\,\mathbf 1_C-\lvert C\rvert\,\mathbf 1_{V\setminus C}$ とおく（$\mathbf 1_C$ は $C$ の特性ベクトル）。辺は $C$ の中か $V\setminus C$ の中にしかないので $Ax=dx$ であり、$x\perp\mathbf 1$、$x\neq0$ である。lem-ab-variational の 2 により $\lambda_2\ge d$ で、$d-2\sqrt{d-1}=(\sqrt{d-1}-1)^2\ge0$ なので $\lambda_2\ge2\sqrt{d-1}$ である。$G_j$ が連結なとき、lem-ab-diameter の最初の不等式の右辺は直径 $D_j$ だけで決まるので、$n_j\to\infty$ なら $D_j\to\infty$ である。$D_j\ge4$ となる $j$ では thm-ab-main の誤差は $(2\sqrt{d-1}-1)/(\lfloor D_j/2\rfloor-1)$ 以下で、$0$ に近づく。2 つの場合を合わせて $\liminf_j\lambda_2(G_j)\ge2\sqrt{d-1}$ を得る。$\square$
Zha23 Theorem 3.6.2（p. 122）は 1 の形を述べ、証明（p. 124）は「$n$ が大きければ距離 $2r+2$ 以上の 2 本の辺がある」ことを使っている。上の証明はその段を直径で書き直したものである。HLW06 Theorem 5.3（p. 484）は、直径 $\Delta$ の $d$-正則グラフについて $\lambda_2\ge2\sqrt{d-1}\,(1-c/\Delta^2)$（$c$ は定数）という、より精密な形を述べている。この記事ではこの精密な形は証明しない。
$2\sqrt{d-1}$ という値の意味
無限の木． すべての頂点の次数が $d$ の無限の木 $\mathbb T_d$ は、どの $d$-正則グラフにも「頂点のまわりを後戻りせずにたどった様子」として現れる（普遍被覆）。HLW06 Theorem 5.2（p. 483）によれば、$\mathbb T_d$ の隣接作用素のスペクトルは区間 $[-2\sqrt{d-1},2\sqrt{d-1}]$ であり、スペクトル半径は $2\sqrt{d-1}$ である（Zha23 p. 122 と Remark 3.6.6、p. 126 も参照）。lem-ab-test の $f$ は、$\mathbb T_d$ の上で 1 本の辺から距離 $i$ の頂点に $(d-1)^{-i/2}$ を置いた関数と同じ形をしている。木の上では距離 $i$ の頂点はちょうど $2(d-1)^i$ 個なので、$a_i=2$ がどの段でも等しく、$Q(f)/f^{\mathsf T}f$ はちょうど $d-2\sqrt{d-1}+\frac{2\sqrt{d-1}-1}{k+1}$ になる。補題の不等式は、$G$ では木より頂点が少ない（閉路があって頂点が重なる）ことを $a_k\le a_i$ の形で使っている。
評価は改良できない． 次数 $d$ を固定して頂点を増やすとき、$\lambda_2$ を $2\sqrt{d-1}$ に限りなく近づけられるかどうかは、Ramanujanグラフ の存在の問題である。Zha23 Theorem 3.6.7（p. 126）によれば、Friedman は、$d$ と $\varepsilon>0$ を固定すると、頂点が $n$ 個の一様に無作為な $d$-正則グラフ（$d$ が奇数なら $n$ は偶数）は、$n\to\infty$ で確率が $1$ に近づくという意味で、$\lambda_2,\dots,\lambda_n$ の絶対値がすべて $2\sqrt{d-1}+\varepsilon$ 以下であることを示した。したがって、定数 $2\sqrt{d-1}$ はこれ以上大きくできない。この記事ではこれを証明しない。
$\lambda(G)$ の形との関係． $\lambda(G):=\max\{\lvert\lambda_2\rvert,\lvert\lambda_n\rvert\}$ とおくと $\lambda(G)\ge\lambda_2$ なので、cor-ab-vertices から $\lambda(G)\ge2\sqrt{d-1}-o(1)$ も従う。この弱い形は、閉じた歩道を数えて $\operatorname{tr}A^{2k}$ を評価する方法でも示せる（エクスパンダーグラフ の定理「Alon–Boppana の評価（$\lambda(G)$ の形）」）。$\lambda_2$ の形が強いのは二部グラフの場合である。二部グラフでは $\lambda_n=-d$ なので $\lambda(G)=d$ で、$\lambda(G)$ の形は何も言わないが、thm-ab-main は二部グラフにも当てはまる。
正の割合の固有値． BH11 Proposition 4.1.2（p. 67）によれば、Serre は、$\varepsilon>0$ と $d$ に応じた定数 $c>0$ があって、頂点が $n$ 個のどの $d$-正則グラフも $(2-\varepsilon)\sqrt{d-1}$ より大きい固有値を $cn$ 個以上もつことを示した。この記事ではこれを証明しない。
例
$d=2$ のとき、ループのない連結な $2$-正則グラフは、頂点が $n\ge3$ 個なら閉路 $C_n$ である。$C_n$ の固有値は $2\cos(2\pi j/n)$（$j=0,\dots,n-1$）なので $\lambda_2=2\cos(2\pi/n)$ であり（隣接行列 の例「閉路グラフ」）、直径は $D=\lfloor n/2\rfloor$ である。$2\sqrt{d-1}=2$ で、thm-ab-main の下界は $2-1/(\lfloor D/2\rfloor-1)$ である。
| $n$ | $D$ | 下界 $2-\frac1{\lfloor D/2\rfloor-1}$ | $\lambda_2=2\cos\frac{2\pi}n$ |
|---|---|---|---|
| $8$ | $4$ | $1$ | $\sqrt2\approx1.414$ |
| $20$ | $10$ | $1.75$ | $\approx1.902$ |
| $40$ | $20$ | $\approx1.889$ | $\approx1.975$ |
$\lambda_2$ は $n\to\infty$ で $2=2\sqrt{d-1}$ に近づき、Alon–Boppana の限界が $d=2$ で正しい値を与えていることが分かる。
$m\ge4$ とし、$m$ 次元超立方体グラフ $Q_m$（二部グラフ の例「超立方体グラフの二部性」）を考える。$Q_m$ は $m$-正則、直径 $m$ で、固有値は $m-2i$（$i=0,\dots,m$）である（BH11 §1.4.6、p. 10）。$\lambda_2=m-2$ は下界 $2\sqrt{m-1}-(2\sqrt{m-1}-1)/(\lfloor m/2\rfloor-1)$ 以上である（$m=4$ で $2\ge1$、$m=6$ で $4\ge2\sqrt5-(2\sqrt5-1)/2\approx2.74$）。$Q_m$ では次数が $m$ とともに増えるので、次数を固定した族ではない。
反例：条件を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 次数 $d$ を固定する | 完全グラフ $K_n$（次数 $n-1$） | $\lambda_2=-1$ で、$2\sqrt{(n-1)-1}=2\sqrt{n-2}$ との差は $n$ とともに限りなく大きくなる |
| $d$-正則（「最大次数が $d$ 以下」に弱める） | 道グラフ $P_n$（$d=3$ とみる） | 最大次数が $3$ 以下で直径 $n-1$ が限りなく増えるのに、$\lambda_2<2<2\sqrt2-0.8$ |
| 直径（頂点の個数）が大きい | 完全グラフ $K_{d+1}$（直径 $1$） | $d$-正則なのに $\lambda_2=-1$ で、$2\sqrt{d-1}$ を大きく下回る |
| 評価する固有値を $\lambda_2$ にする（$\lvert\lambda_n\rvert$ に替える） | 角柱グラフ $C_m\square K_2$ の線グラフ（$4$-正則） | 頂点がいくらでも多いのに、$\lvert\lambda_n\rvert\le2<2\sqrt3-1.4$ |
各行で外した条件が 1 つであり、結論が崩れることを確かめる。
各行の確認を開く
1 行目：$K_n$ の固有値は $n-1$ と $-1$（重複度 $n-1$）なので、$n\ge3$ で $\lambda_2=-1$ である（隣接行列 の例「完全グラフと完全二部グラフ」）。$K_3,K_4,\dots$ は頂点の個数が $\infty$ に発散するループのない正則グラフの列で、cor-ab-vertices の 1 の条件のうち外れているのは「次数 $d$ を固定する」だけである。
2 行目：$P_n$（頂点 $v_1,\dots,v_n$、$v_j$ と $v_{j+1}$ が隣接）の隣接行列について、$x_j:=\sin(\pi lj/(n+1))$（$l=1,\dots,n$）とおくと $x_0=x_{n+1}=0$ と $\sin(a(j-1))+\sin(a(j+1))=2\cos a\,\sin(aj)$ から $(Ax)_j=2\cos\frac{\pi l}{n+1}\,x_j$ である。これらは $n$ 個の相異なる固有値なので、固有値は $2\cos\frac{\pi l}{n+1}$ ですべて $2$ より小さい。$2\sqrt2-0.8\approx2.03>2$ であり、直径 $D\ge8$ では $d=3$ の thm-ab-main の右辺は $2\sqrt2-(2\sqrt2-1)/3\approx2.22$ 以上なので、$P_n$（$n\ge9$）の $\lambda_2$ はこれを下回る。$P_n$ はループのない連結グラフで、直径 $n-1$ で、外れているのは正則性だけである。
3 行目：$K_{d+1}$ の固有値は $d$ と $-1$ である。頂点の個数を固定した 1 つのグラフなので、cor-ab-vertices の 1 には当てはまらず、thm-ab-main の $D\ge4$ もみたさない。
4 行目：$H:=C_m\square K_2$（$m\ge3$）は 2 つの $m$ 角形の対応する頂点を辺で結んだ $3$-正則単純グラフで、その線グラフ $L(H)$（$H$ の辺を頂点とし、端点を共有する 2 辺を隣接させる）は $4$-正則単純グラフで、頂点は $3m$ 個である。$H$ の頂点と辺の接続行列を $B$（頂点 $v$ が辺 $e$ の端点なら $B_{ve}=1$、そうでなければ $0$）とすると、$(B^{\mathsf T}B)_{ee}=2$、$e\neq e'$ なら $(B^{\mathsf T}B)_{ee'}$ は共有する端点の個数（$H$ は単純なので $0$ か $1$）なので、$B^{\mathsf T}B=2I+A_{L(H)}$ である。$x^{\mathsf T}B^{\mathsf T}Bx=(Bx)^{\mathsf T}(Bx)\ge0$ なので、$A_{L(H)}$ の固有値はすべて $-2$ 以上である。一方 $2\sqrt3-1.4\approx2.06>2$ である。$L(H)$ は連結な $4$-正則グラフなので lem-ab-diameter により直径は $m$ とともに限りなく大きくなり、直径 $D\ge6$ では $d=4$ の thm-ab-main の右辺は $2\sqrt3-(2\sqrt3-1)/2\approx2.23$ 以上である。$\lambda_2$ をこれで抑える形は成り立つが、$\lvert\lambda_n\rvert$ に替えた形は成り立たない。最小固有値については Alon–Boppana の形の下界は成り立たない。
関連項目
- 前提: 正則グラフ, 隣接行列, Rayleigh商, グラフの距離
- 等号の側: Ramanujanグラフ
- 比較: エクスパンダーグラフ, Cheegerの不等式(グラフ), Laplacian行列
- 分野: スペクトルグラフ理論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
