高次元エクスパンダー: マトロイドの局所エクスパンダー性

今回も高次元エクスパンダーに関する記事となります。前回の記事では単体複体の局所エクスパンダー性を定義し、Oppenheimのトリクルダウン定理を紹介しました。今回の記事ではその応用として以下の前回の記事でも紹介した以下の系を証明したいと思います。

系2.

マトロイド$(V,\mathcal{F})$は局所$0$-エクスパンダーである。

軽く定義を復習しましょう。考えるマトロイドを$X=(V,\mathcal{F})$とし、そのランクを$d$とします。したがって$X(d-2)$は要素数$d-2$の独立集合の全体です。独立集合$\sigma\in X(d-2)$を一つ固定し、そのリンク$X_\sigma$の1-スケルトン$G_\sigma$を考えます。このグラフ$G_\sigma=(V\setminus \sigma,E)$は次で与えられます:

$$\{u,v\}\in V \iff \sigma\cup \{u,v\} \in \mathcal{F}.$$

$G_\sigma$上の単純ランダムウォーク(隣人を一様ランダムに選んで遷移するランダムウォーク)の遷移確率行列を$P_\sigma$とし、$\lambda_2(P_\sigma)$をその2番目に大きい固有値とします。

マトロイドの基の交換を繰り返せば任意の二つの基の間を行き来することができます（詳細は例えばこちらのページの定理1を参照）。同様の議論により、マトロイドはトリクルダウン定理の条件(1-スケルトングラフの連結性)を満たし、トリクルダウン定理の系1より、$\mu_{d-2} = \max_{\sigma\in X(d-2)}\lambda_2(P_\sigma)\leq 0$を示せば冒頭の系2が得られます。

マトロイドに対する$G_\sigma$はどのようなグラフなのでしょうか。実は非常に特徴的な構造を持つことがわかります:

補題1.

任意の$\sigma\in X(d-2)$に対して$G_\sigma$の補グラフの全ての連結成分はクリークである。

証明:

$G_\sigma=(W,E)$とします。$\{u,v\},\{v,w\}\not\in E$ならば$\{u,w\}\not\in E$を背理法を使って示します。まず$\{u,w\}\in E$を仮定します。$G_\sigma$の定義より$S_1:=\sigma\cup \{u,w\}\in \mathcal{F}$です。また、$v$は$G_\sigma$の頂点なので$S_2:=\sigma\cup\{v\}\in\mathcal{F}$も成り立ちます。$S_1,S_2$に対して独立集合族の公理を適用すると$S_2\cup \{u\}\in \mathcal{F}$または$S_2\cup \{w\}\in\mathcal{F}$の少なくとも一方が成り立ちます。しかしこれは$\{u,v\},\{v,w\}\not\in E$に矛盾します。

（証明終）

$G_\sigma$の補グラフの各連結成分を$C_1,\dots,C_\ell\subseteq V$とします。$C_1,\dots,C_\ell$は、補グラフにおける孤立点(次数0の頂点)に対応する連結成分も含みます (例えば$C_1=\{v_1\}$にもなりえるということです)。各$C_i$の指示ベクトルを$v_i$として全ての要素が1の行列を$J$とすると、$G_\sigma$の隣接行列$A$は

\begin{align*} A = J - \sum_{i=1}^\ell v_iv_i^\top\end{align*}

と表せます。したがってCauchyのinterlacing定理より$\lambda_2(A)\leq 0$を得ます。

定理 (Cauchyのinterlacing定理).

対称行列$A\in\mathbb{R}^{n\times n}$の固有値を$\alpha_1\geq \dots \geq \alpha_n$とする。ベクトル$v\in\mathbb{R}^n$に対し、行列$A-vv^{\top}$の固有値を$\beta_1\geq \dots \geq \beta_n$とする。このとき

\[ \alpha_1 \geq \beta_1 \geq \dots \geq \alpha_n \geq \beta_n.\]

特に, $\lambda_2(A-vv^{\top})\leq \lambda_2(A)$.

さて、$G_\sigma$の次数行列$D$と隣接行列$A$を用いて$P_\sigma=D^{-1}A$と表せます。さらに$\lambda_2(A)\leq 0$です。また、$\lambda_2(P_\sigma)=\lambda_2(D^{-1/2}AD^{-1/2})$およびSylvesterの慣性法則により$D^{-1/2}AD^{-1/2}$と$A$の正の固有値の個数は一致するため、$\lambda_2(P_\sigma)\leq 0$を得ます。

定理 (Sylvesterの慣性法則)

対称行列$A\in\mathbb{R}^{n\times n}$と正則行列$S$に対して、$A$と$SAS^\top$の①正の固有値の個数、②負の固有値の個数、③ゼロ固有値の個数は全て一致する。

高次元エクスパンダー: 局所エクスパンダー性の定義とOppenheimのトリクルダウン定理

前回に引き続き高次元エクスパンダーの導入をします。前回の記事では単体複体に関する基本的な用語を定義しました。今回の記事では(純粋な)単体複体に対してエクスパンダー性という性質を定義します。

グラフのエクスパンダー性

元来「エクスパンダー性」という用語はグラフに対して定義される用語です。本記事ではグラフのエクスパンダー性の最低限の定義を述べます。詳しく知りたい方は私が以前mathlogで執筆したこちらの記事をご覧ください。

本記事でグラフと言えば有限集合$V$と2元部分集合族$E\subseteq\binom{V}{2}$の組$(V,E)$で定義されます. 関数$w\colon E\to\mathbb{R}_{\geq 0}$を辺重みと呼び、三つ組$(V,E,w)$を重み付きグラフ (または辺重み付きグラフ) と呼びます。辺の向き、多重辺、自己ループは考えません。

重み付きグラフ$(V,E,w)$に対して重み付き隣接行列$A\in\mathbb{R}_{\geq 0}^{V\times V}$を

\begin{align*} A(u,v) = \begin{cases} 0 & \text{if $\{u,v\}\not\in E$},\\ w(\{u,v\}) & \text{ if $\{u,v\}\in E$} \end{cases} \end{align*}

と定義します。重み付き次数行列$D\in\mathbb{R}_{\geq 0}^{V\times V}$を

\begin{align*} D(u,v) = \begin{cases} 0 & \text{if $u\neq v$},\\ \sum_{w\in V} A(u,w) & \text{ if $u=v$} \end{cases} \end{align*}

とします。最後に遷移確率行列$P$を

\begin{align*} P=D^{-1}A \end{align*}

とします。直感的には頂点$u$からスタートして辺重みに比例した確率で隣接点$v$に移動するランダムウォークを考えたとき、$P(u,v)$の値は頂点$u$から$v$に遷移する確率と等しくなります。なお、$w$を正の定数倍をしても行列$P$は不変です。

$P$は確率行列(各行和が1)なので全ての頂点$u\in V$に対して$\sum_{v\in V}P(u,v)=1$となります。これを行列の形で書くと$P\mathbb{1}=\mathbb{1}$です ($\mathbb{1}\in\mathbb{R}^V$は全ての成分が$1$のベクトル)。すなわち$P$は固有値$1$を持ち、対応する固有ベクトルは$\mathbb{1}$です。この記事の命題1から$P$の他の固有値も全て実数になることが示せます。これらを大きい順に並べて$1=\lambda_1\geq \lambda_2\geq\dots\geq\lambda_{|V|}$とし、これらを第一固有値、第二固有値、などと呼びます。$\lambda_2\leq\lambda$を満たすような重み付きグラフ$G=(V,E,w)$を$\lambda$-エクスパンダーといいます(注)。行列$P$の第二固有値を$\lambda_2(P)$と表します。

注：本来はエクスパンダー性は$\max\{\lambda_2,|\lambda_{|V|}\}\leq\lambda$を満たすグラフとして定義されますことが多いです。ここでは非自明な固有値が絶対値の意味でバウンドされていることを要請しています。しかし単体複体上のランダムウォークの文脈では片側だけのバウンドで事足りるので、ここでは$\lambda_2$の上界のみを考えます。とりあえず$\lambda_2$が小さければ小さいほど良いエクスパンダーであると思ってください。

基本的に考えるグラフは連結であるとします。非連結なグラフの場合、各連結成分の指示ベクトルが固有ベクトルとなり固有値1の多重度が2以上になるからです。

例: 完全グラフ

$G=(V,E,w)$をunit weightの$n$頂点の完全グラフとします。すなわち$|V|=n$で$E=\binom{V}{2}$であり、さらに$w(\{u,v\})=1$とします。全ての成分が$1$の行列を$J$、単に行列を$I$と表すと、$G$の隣接行列は$J-I$と表せます。この行列の第二以降の固有値は全て$-1$なので、遷移確率行列は$\lambda_2=\dots=\lambda_n=-\frac{1}{n-1}$となるので、$G$は$\left(-\frac{1}{n-1}\right)$-エクスパンダーです。

単体複体のエクスパンダー性 (局所エクスパンダー)

重み$w$を持つ純粋な$d$次元単体複体$X=(V,\mathcal{F})$を考えます。次元$k$以下の面全体からなる単体複体$X_k=(V,\mathcal{F}_k)$を$k$-スケルトン ($k$-skelton) といいます。元の単体複体$X$が重み付きならば$k$-スケルトンも同じ重みを考えて重み付きとみなします。

特に$1$-スケルトン$X_1=(V,\mathcal{F}_1)$はグラフ$(V,X(1))$とみなせます。$X$が重み付きならば辺重みを$w_1\colon X(1)\to\mathbb{R}_{\geq 0}$とすることで重み付きグラフ$(V,X(1),w_1)$を考えることができます。これを$X$の$1$-スケルトングラフと呼ぶことにします。

面$\sigma\in\mathcal{F}$のリンク$X_\sigma$に対してその$1$-スケルトングラフを$G_\sigma$とします ($\dim\sigma \leq d-2$とします)。これの遷移確率行列を$P_\sigma$とします。全ての$G_\sigma$が$\lambda$-エクスパンダーであるとき、$X$は局所$\lambda$-エクスパンダーであるといいます。基本的に全ての$G_\sigma$は連結であるとします。

特に、$X$の重み$w_d\colon X(d)\to\mathbb{R}_{\geq 0}$が非ゼロの定数関数ならば、各面$\sigma\in X(d-2)$のリンク$X_\sigma$がなす$1$-スケルトングラフの辺重みは全て同じ値になる (つまり正規化すれば重みなしグラフとみなせる) ことに注意してください。

例: 完全単体複体

各$-1\leq k\leq d$に対して$X(k)=\binom{V}{k+1}$を満たす単体複体を$d$次の完全単体複体と呼びます。これは完全グラフを単体複体に拡張したものになっています。unit weightを考えます (すなわち$w_d(\sigma)=1 (\forall \sigma\in X(d))$で重みづけする)。$\sigma\in X(k)$に対しグラフ$G_\sigma$は$|V|-|\sigma|$頂点の完全グラフとなり、辺重みは一様なので、$\left(-\frac{1}{|V|-|\sigma|-1}\right)$-エクスパンダーです。

Oppenheimのトリクルダウン定理

重み付き単体複体を考えたとき、再帰的に定義された面の重みで定まる行列の固有値を計算することはとても難しく、定義通りにやろうとすると完全単体複体など簡単なものでしかなかなかできないとおもいます。Oppenheimのトリクルダウン(tricling down)定理は次元$k$の面のエクスパンダー性を次元$k+1$の面のエクスパンダー性に帰着する定理です。

$X$を純粋な$d$次元単体複体とします。各$-1\leq k\leq d-2$に対して

\begin{align*} \mu_k = \max_{\sigma\in X(k)} \lambda_2(P_\sigma) \end{align*}

とします。

定理 (Oppenheimのトリクルダウン定理; [1]).

全ての$G_\sigma$が連結であるならば、各$-1\leq k< d-2$に対して\[\mu_k \leq \frac{\mu_{k+1}}{1-\mu_{k+1}}.\]

trickling downとはあえて和訳すると「浸透」という意味です。経済学には「trickle-down」(トリクルダウン)という用語があるらしく、経済活動の活性化が富裕層から下級層に浸透していくみたいな意味があるらしいです。この定理は高次元リンクのエクスパンダー性が低次元リンクに「トリクルダウン」することを主張しています。2018年に証明された定理ですが高次元エクスパンダーの文脈ではOppenheim's Trickling Down Theoremと呼ばれています。知名度の高い和訳はまだないと思いますが、これに倣って私も脳内で「トリクルダウン定理」と呼んでいます。

系1.

$\mu_{d-2}\leq 0$ならば$X$は局所$0$-エクスパンダーである。

すなわち、局所エクスパンダー性を示すには次元$d-2$の面だけ考えれば良いということになります。完全単体複体の例の直前の段落でも述べましたが次元$d-2$の面であれば重み関数も簡単な形になるので局所エクスパンダー性の確認が容易になります。特に、トリクルダウン定理を使うと以下を証明することができます。

系2.

マトロイド$(V,\mathcal{F})$は局所$0$-エクスパンダーである。

端的に言えば系2は「マトロイドはエクスパンダーである」ことを主張しています。グラフエクスパンダーの文脈ではエクスパンダー性はランダムウォークのrapid mixingに直結するのですが似たようなことが単体複体にも成り立ちます。

次回の記事ではトリクルダウン定理を用いて系2の証明を行います。その次の記事でトリクルダウン定理の証明を行います。

文献

[1]. Oppenheim, Izhar. 2018. “Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps.” Discrete & Computational Geometry 59 (2): 293–330. https://doi.org/10.1007/s00454-017-9948-x.

高次元エクスパンダー: 単体複体とマトロイド

理論計算機科学では近年、高次元エクスパンダーという概念が流行しています。以前の記事でマトロイドの基の一様サンプリングの論文を名前だけ述べました. 理論的な背景としてマトロイドの独立集合族の「エクスパンダー性」が重要になるのですが, この辺りについて最近勉強したので整理していきます.

全体の要約：

• 部分集合で閉じた集合族を単体複体(または独立性システム)という. 特にマトロイドは単体複体の特殊ケースである.
• グラフに対して定義されるエクスパンダー性という性質を単体複体に拡張する.
• マトロイドの独立集合族はそのエクスパンダー性を満たす.
• 飛び道具を使うと基上のランダムウォークのrapid mixingが言えてMCMCが可能になる.

最終目標は証明まで理解することです. 本記事ではその準備として, 単体複体の基本概念を定義していきます.

単体複体

有限集合$V$とその上の部分集合族$\mathcal{F}\subseteq 2^V$の組$X=(V,\mathcal{F})$を考える. $\mathcal{F}$が部分集合で閉じている(すなわち, $\tau\subseteq \sigma$かつ$\sigma\in\mathcal{F}$ならば$\tau\in\mathcal{F}$)とき, $X$を単体複体(simplicial complex)といいます.

単体複体$X=(V,\mathcal{F})$に対し, $\sigma\in\mathcal{F}$を面(face)といい, その次元を$\dim\sigma = |\sigma|-1$で定めます. $\max_{\sigma\in\mathcal{F}}\dim\sigma=d$のとき, $X$は$d$次単体複体といいます. 全ての極大な面の次元が同じとき, $X$は純粋(pure)であるといいます. 各$0\leq k\leq d$に対して$X(k)=\{\sigma\in\mathcal{F}\colon \dim\sigma=k\}$とします. 純粋な$d$次単体複体$X=(V,\mathcal{F})$と各$0\leq k\leq d$に対して$X(k)=\{\sigma\in\mathcal{F}\colon \dim\sigma=k\}$とします. 

幾何的に解釈すると, $0$次の面は点$\{v\}$, $1$次の面は線分$\{u,v\}$, $2$次の面は三角形$\{u,v,w\}$, ...など, 一つ一つの面は単体とみなすことができます.

純粋な$d$次単体複体$X$に対して, 関数$w_d\colon X(d)\to\mathbb{R}_{\geq 0}$を考えます. $0\leq k\leq d-1$に対して$w_k\colon X(k)\to\mathbb{R}_{\geq 0}$を

• $w_k(\sigma) = \sum_{\tau\in X(k+1),\tau\supset \sigma} w_{k+1}(\tau)$

で再帰的に定義し, 重み関数$w\colon \mathcal{F}\to\mathbb{R}_{\geq 0}$を$w(\sigma)=w_{\dim(\sigma)}(\sigma)$で定義します.

面$\sigma\in\mathcal{F}$のリンク$X_\sigma=(V_\sigma,\mathcal{F}_\sigma)$を

\begin{align*} V_\sigma &= \{v\in V\setminus\sigma\colon \sigma\cup \{v\}\in\mathcal{F}\},\\ \mathcal{F}_\sigma &= \{\tau\setminus \sigma\colon \tau\in \mathcal{F},\tau\supseteq \sigma\} \end{align*}

と定義します. リンクもまた単体複体になっており, $X$が純粋な$d$次単体複体ならば$X_\sigma$は純粋な$d-|\sigma|$次単体複体となります.

重み付き単体複体はそのリンク$X_\sigma$に対して以下のように重み$w^\sigma\colon X_\sigma\to\mathbb{R}_{\geq 0}$を誘導します:

\[w^\sigma(\alpha)= \frac{w(\sigma\cup \alpha)}{w(\alpha)}.\]

単体複体に対して以下のような包含関係を表した階層構造(ハッセ図)を想起するのが良いと思います. 

例1. マトロイド

単体複体の重要な例としてマトロイドがあります. 定義などの丁寧な説明はこちらのページにもありますが, 本記事でも簡単に紹介します. マトロイドとは単体複体$(V,\mathcal{F})$であって次の性質を満たすものです:

$|\sigma|<|\tau|$を満たす任意の$\sigma,\tau\in\mathcal{F}$に対してある$v\in\tau\setminus\sigma$が存在して$\sigma\cup\{v\}\in \mathcal{F}$.

この性質よりマトロイドは純粋な単体複体です. 実際, 二つの相異なる極大な面$\sigma,\tau\in\mathcal{F}$が$|\sigma|<|\tau|$を満たすならば上の性質より$\sigma$の極大性に反します. マトロイドを純粋な単体複体とみなしたときの次元に1を加えたものを階数(rank)といいます.

例. グラフ$G=(U,E)$の辺部分集合であって閉路を含まないもの全体からなる辺部分集合族はマトロイドになり, 特にグラフ的マトロイド(graphic matroid)といいます.

例. 体$K$上の行列$A\in K^{n\times m}$の各行を$[n]=\{1,\dots,n\}$で番号付けし, 各行ベクトルを$a_1,\dots,a_n$とします. $[n]$上の部分集合族$\mathcal{F}\subseteq 2^{[n]}$を, 

$F=\{i_1,\dots,i_k\}\in\mathcal{F}\iff$$a_1,\dots,a_{i_k}$が線形独立

で定義したとき, $([n],\mathcal{F})$はマトロイドになり, 特に線形マトロイド(linear matroid)と呼びます.

Remark: 単体複体の文脈では台集合$V$は頂点とみなしますが, (組合せ最適化の文脈における)マトロイドは台集合は辺とみなし$E$で表すことが多いです. 

例2. マトロイド交叉

同じ台集合上の二つのマトロイド$(V,\mathcal{F}_1),(V,\mathcal{F}_2)$に対し,

\[ \mathcal{F}_1\cap \mathcal{F}_2 = \{F\subseteq V\colon F\in \mathcal{F}_1\cap \mathcal{F}_2\}\]

を共通独立集合と呼びます. 組合せ最適化の文脈では共通独立集合のうち要素数最大のものを求める問題はマトロイド交叉問題と呼ばれ, 独立性オラクル(部分集合が$\mathcal{F}_i$に属すかどうかを返すオラクル)があれば多項式時間で解けることが知られています.

共通独立集合の族$\mathcal{F}$に対し, $(V,\mathcal{F})$は単体複体になりますが, 考えるマトロイドによっては必ずしも純粋になるとは限りません.

強正則グラフのスペクトル解析と未解決問題への応用

0. 背景

グラフ理論とは文字通り, グラフについて解析する分野です. グラフ理論のモチベーションとしては, 「最小全域木」「最大マッチング」「最大フロー」などのアルゴリズムを考える際に対象となるオブジェクト(この例で言えば全域木, マッチング, フロー)に対する「良い」特徴付けや性質(例えばHallの結婚定理, グラフマトロイドの基, 交互増加道, 残余ネットワークに関するものなど)を与えるという, アルゴリズム上のモチベーションが最も大きいんじゃないかと思います.

しかしそれとは別に純粋数学寄りな一面もあります. グラフ理論の一分野に「Algebraic graph theory」というのがあります. 直訳すると「代数的グラフ理論」で, この分野はグラフの特徴を代数的に解析するもしくは代数的に「綺麗な」グラフを構成したり, Tutte多項式といった興味深い不変量について解析しています. ここで言う「代数」とは線形代数(スペクトラムグラフ理論)や群(Cayley graph)などです. 面白いことに正則グラフ(全ての頂点の次数がある定数に等しいグラフ)に対するゼータ関数としてIhara zeta function というものが知られていて, Ihara zeta function を用いてラマヌジャングラフと呼ばれるスペクトラムグラフ理論において非常に重要なグラフの特徴づけを与えられています.

グラフの持つ美しい性質の解析の一方で, こちらの記事で紹介したような「小直径グラフを構成する」や「彩色数と内周(girth)が共に大きいグラフ」といった, 普通のグラフでは満たされないような性質を満たすグラフをalgebraic graph theoryの道具を用いて巧妙に構成するという研究も有ります.

今回の記事では 強正則グラフ (strongly regular graph) と呼ばれるグラフについて, スペクトラムグラフ理論においてしばしば用いられるテクニック(=線形代数)を用いて解析していきます. 更にその応用として, グラフ理論における二つの未解決問題(Moore graph と Conway 99 problem)について考察してみます. あらかじめ記しておきますが, 本記事は予想以上に線形代数成分が強いです (というかグラフ理論成分は少なめです).

1. 強正則グラフ

グラフ$G$に対し, その頂点$v$に隣接する頂点の全体を$N(v)$で表します.
$n$頂点の$k$-正則グラフ$G$ (全ての頂点の次数が$k$に等しいグラフ) が以下の全ての性質を満たすとき, $G$はパラメータ$(n,k,\lambda,\mu)$を持つ強正則グラフであると言います.

1. 任意の隣接する二頂点$u,v$に対して, $|N(u)\cap N(v)|$がある定数$\lambda$に等しい.
2. 任意の隣接しない二頂点$u,v$に対して, $|N(u)\cap N(v)|$がある定数$\mu$に等しい.

イメージとしてはこんな感じです:

特に, $\mu>0$の場合はグラフの直径は$2$以下となります. $\mu=0$の場合はグラフは非連結で, 各連結成分はサイズ$\lambda+2$の完全グラフになっていて次数は$k=\lambda-1$となります.

例:

・長さ5の閉路 : $(n,k,\lambda,\mu)=(5,2,0,1)$.

・Petersen graph : $(n,k,\lambda,\mu)=(10,3,0,1)$.

Petersen graph

・$n$頂点の完全グラフ : $(n,k,\lambda,\mu)=(n,n-1,n-2,0)$.

・長さ$3$の閉路 : $(n,k,\lambda,\mu)=(3,2,1,0)$.

$\lambda$は三角形の個数, $\mu$は四角形の個数を規定している感じになっています.

2. 強正則グラフのスペクトル

$G$を$(n,k,\lambda,\mu)$をパラメータに持つ強正則グラフとします. 更に$\mu\neq 0$を仮定します. $G$の隣接行列を$A$とします. すなわち

と定めます. 今回の目的は$A$の全ての固有値を特定することです. 固有値を求めてそこから得られる様々な条件を考えることによって, 与えられたパラメータ$(n,k,\lambda,\mu)$に対応する強正則グラフの存在性について議論することが出来ます (後述).

$i\neq j$に対し, $(A^2)_{ij}$は頂点$i$から頂点$j$への長さ2のパスの本数に等しいはずです. $ij$が隣接しているときはこの値は$\lambda$と等しく, そうでないときは$\mu$に等しくなります (上図参照). $i=j$に対しては$A^2_{ij}$は次数に等しいので$k$となります. 以上より

なので, 

$A^2+(\mu-\lambda)A=(k-\mu)I+\mu J$                    ...(1)

となります. ここで $I$ は$n\times n$の単位行列, $J$は全ての要素が1に等しい$n\times n$行列です. 即ち強正則グラフの隣接行列は行列の二次方程式が成り立ちます.

$A$は$k$-正則グラフなので, 各行に含まれる$1$の個数(=次数)は全て$k$に等しいはずです. すなわち $A\mathbb{j}=k\mathbb{j}$ が成り立ちます. ここで$\mathbb{j}\in\mathbb{R}^n$は全要素が$1$の列ベクトルです. 更に$A$対称行列なので全ての固有値は実数であり, しかも最大固有値は$k$に等しく, ($\mu>0$よりグラフは連結なので, $A$は行列として既約であるため, ペロン=フロベニウスの定理より)最大固有値の多重度は$1$となります. したがって$A$の他の固有値$\theta$に対応する固有ベクトル$x$は必ず$\mathbb{j}$と直交します. このベクトル$x$を二次方程式の両辺に掛けると, ($Jx=\mathbb{j}\mathbb{j}^{T}=0$に留意して)

$(A^2+(\mu-\lambda)A)x = (\theta^2+(\mu-\lambda)\theta)x = (k-\mu)x$

となります. したがって$\theta$は以下の二次方程式:

$\theta^2+(\mu-\lambda)\theta-(k-\mu)=0$

の解になっているので, 

以上より, $A$の固有値は三種類しかなく, それらは

となることが分かりました. 更に, $A$に関する二次方程式の両辺に$\mathbb{j}$を掛けると

$k^2+(\mu-\lambda)k=k-\mu+\mu n$                    ...(2)

即ち, $k(k-\lambda-1)=(n-k-1)\mu$ が成り立ちます.

最後に, それぞれの多重度を求めてみましょう. 

とおいてそれぞれの多重度を$s,t$とおきます. すると$A$のトレース(=対角成分の和=固有値の和)は$0$に等しく, 固有値$k$の多重度は$1$であることも合わせると

$fs+gt+k=0$, $s+t=n-1$

となり, これを連立させると

                    ...(3)

が成り立ちます. 即ち $(n,k,\lambda,\mu)$をパラメータとして持つような強正則グラフが存在するためには, これら四つの値が (2)を満たしかつ(3)で与えられる$s,t$が整数とならなければいけません. これらの条件を使うことによって与えられたパラメータに対応する強連結グラフの存在性について議論することが出来ます.

先ほどみたように, 連結な強正則グラフの固有値は3種類しかありません. 面白いことに逆も成り立つことが知られています:

定理1:

$G$を連結な$k$-正則グラフで完全グラフでないものとする. $G$の隣接行列が三つの相異なる固有値$k>s>t$を持つとする. このとき, $G$は強正則グラフである.

また一般に, 固有値の種類数はグラフ(強正則でなくても良い)の直径を上から抑えるということが知られています:

定理2:

連結な$G$に対してその隣接行列が持つ相異なる固有値の個数を$m$とする. $G$の直径は$m-1$以下である.

強正則グラフは固有値は3種類しかないので直径2となっていますが, このことは定理2と整合性がとれています (余談ですが, 定理2の証明は2016年に東京大学情報理工学系研究科の数理情報学専攻の修士課程の大学院入学試験で出題されました).

応用1: Moore graph の存在性

Moore graph とは簡単に言うと「直径$D$の$d$-正則グラフの中で最も頂点を多く含んでいるグラフ」のことです. 詳しくはこちらの記事に書いてあります. Moore graphは

1. 直径$>2$の場合は存在しない
2. 直径$=2$かつ$d\not \in \{2,3,7,57\}$ の場合は存在しない.

ことが示されています. 今回は二つ目の事実をこれまでの議論を使って示していきます. こちらの記事より, 直径2のグラフ$G$が Moore graph であることの必要十分条件は, $G$が三角形と四角形を含まないことです. 更に, 明らかに$n=k^2+1$となります). 従って, $G$はパラメータ$(n,k,\lambda,\mu)=(k^2+1,k,0,1)$を持つ強正則グラフとなっていることに注意します($n=k^2+1$は今回導出した(2)の条件に$\lambda=0,\mu=1$を代入することで導出できます).

(3)の整数性条件を考えます. パラメータを代入して計算すると

即ち, $k^2-2k=0$ もしくは $4k-3=p^2$ ($p\in\mathbb{N}$) が必要条件となります. $k^2-2k=0$, 即ち$k=2$に対しては長さ$5$の閉路が対応しています. ２番目の条件より, $k=(p^2+3)/4$ を $s$ に代入すると,

$s=\frac{p^4+6p^2+9}{32}+\frac{p^4-2p^2-15}{32p} = \frac{p^5+p^4+6p^3-2p^2+9p-15}{32p}$

整理すると

$p^5+p^4+6p^3-2p^2+(9-32s)p=15$

従って$p$は$15$を割り切るので, $p\in \{1,3,5,15\}$となり, それぞれの$p$を$4k-3=p^2$に代入ことにより, $k=1,3,7,57$ が得られます. $k=1$の時は$n=k^2+1=2$より, グラフは$K_2$となります (直径2ではないのでこれは除外します).

従って, 直径2のMoore graphが存在するならば, $k\in \{2,3,7,57\}$ が成り立ちます.

応用2: Conway 99 graph problem

元ネタ : https://oeis.org/A248380/a248380.pdf
関連文献 : https://arxiv.org/abs/1707.08047

こちらの問題はグラフ理論というよりは, Conwayが出した未解決な問題であり, 解けたら1000ドルもらえるというプチミレニアム未解決問題です. 具体的には次のような問題です:

問題: 以下の二つの性質を満たす$99$頂点のグラフは存在するか否か.

1. 任意の隣接している二頂点$u,v$に対して, $u,v$を含む三角形が唯一存在する.
2. 任意の隣接していない二頂点$u,v$に対して, $u,v$を対角線上に含むような四角形が唯一存在する.

イメージとしては次のような感じです:

三角形は被ってはいけない. 四角形は二辺を共有してはいけない.

本記事では条件1を三角形条件, 条件2を四角形条件と呼ぶことにします (番号が乱立して可読性が下がるため)

問題を見た感じだと正則グラフには見えないのですが, もし所望のグラフ$G$が存在するとして, それが$k$-正則であったならば, $G$はパラメータ$(99,k,1,1)$を持つ強正則グラフであることが分かります. すると(2)の条件より, $k=14$が出てきます. そもそもなぜ頂点数が99なのでしょうか？この記事ではより一般に, パラメータ$(n,k,1,1)$を持つ強正則グラフについて考え, どのような$n$と$k$に対してそのグラフが存在するのかについて考えていきます.  まず明らかですが, $n=3,k=2$に対しては$K_3$が所望の性質を満たすことが確認できます(非隣接点が存在しないため). これ以外に所望のグラフはあるのでしょうか？

実は, 所望のグラフが存在するとしたら, そのグラフは必ず正則であることが次のようにして証明できます:

$G=(V,E)$の頂点数を$n$とします. $G$において隣接している二頂点$u,v$を任意にとってきます. するとある頂点$w\in V\backslash \{u,v\}$が一意に存在して$uvw$が三角形となります. 更に$n\geq 4$のとき, $G$の直径は$2$であり, $k\geq 3$となる ($k=2$ならば$n=3$となってしまうから). 従って$u$に隣接する頂点$z\in V\backslash \{v,w\}$が存在し, この$z$はどれも$v$には隣接していない (そうでないならば, $uvz$が三角形条件に反する. 下図1参照).

図1 : $z$と$v$は隣接してはいけない.

　そこで$z, v$に対して四角形条件を適用すると, $zv$を対角線として持つような四角形$uvz'z$が存在することになります. 特にこの四角形は一意なので, $z$に対して$z'$は唯一定まります (図2). 特に$z'\in N(v)$に注意します.

図2. $vz$を対角線に持つような四角形がとれる. 一方で$z$に対して複数の$z'$をとることは出来ない.

そこで写像$z\mapsto z'\in N(v)$を考えると, これは単射になっています. $z_1\neq z_2 \in N(u)$に対して$z_1\mapsto z'$, $z_2\mapsto z'$となると四角形条件に反するからです.

図3: $z_1,z_2 \mapsto z'$となると$uz'$を対角線に持つ四角形が二つできてしまう.

従って, 単射$N(u)\to N(v)$が構成できた(実際は全単射になっている)ので, $|N(u)|\leq |N(v)|$. 同様にして逆も言えるので, $|N(u)|=|N(v)|$. $G$は連結なので, どの頂点の次数もある定数に等しい. よって$G$は正則である.

以上より, 議論すべきグラフは正則なので, パラメータ$(n,k,1,1)$を持つ強正則グラフです. 更に(2)の条件より, $n=\frac{k^2}{2}+1$となります. $n$の整数性から$k$が偶数であることも直ちに従います. さらに, 固有値の多重度の整数性条件から





すなわち$k^2-4k=0$, $4k-7=p^2$となります.

$k^2-4k=k(k-4)=0$の場合は$k=4$となり, 対応する$n$は$n=\frac{k^2}{2}+1=9$.

$4k-7=p^2$の場合は$k=(p^2+7)/4$を$s$に代入することにより





従って, $p^5+p^4+14p^3-2p^2+(49-64s)p=63$ となるので, $p$は$63$を割り切ります. 即ち$p\in \{1,3,7,9,21,63\}$. 対応する次数$k$は$k\in\{2,4,14,22,112,994\}$.

まとめると, $(n,k,1,1)$をパラメータとして持つ強正則グラフが存在するための十分条件は(計算ミスがなければ)





実際, $(n,k)=(3,2)$に対しては$C_3$が対応しています. しかし$(n,k)=(9,4)$に対しては存在しないことが示せます(三角形条件と四角形条件を使って局所的な構造を絞ることによって示せますがあまり証明としては綺麗ではありません). こちらにあるように, $(n,k)=(9,4)$は具体的にグラフが構成でき, 隣の研究室の後輩に教えられたのですが, $K_{3,3}$の線グラフ(辺と頂点を交換したグラフ)が条件を満たしています. (2018年7月24日追記) $(n,k)=(99,4)$はConwayの99問題に対応しています. 他にも三つほどヤバそうな$(n,k)$がありますが, とりあえず有限個であることは以上の議論より示すことが出来ました.

要するに「99」という数字の本質は線形代数的な議論によって導かれます. また, Moore graphにおいても「次数57」の条件は同様な議論から導出できます. 即ち「良い性質を持った」グラフの存在性については未だに線形代数的な議論によってしか条件を絞り込むことが出来ていないというのが現状です. 従って今回提示した二つの未解決問題を解くためには, 線形代数から少し離れたアプローチ, もしくはよりグラフ理論っぽいアプローチから新たな必要条件を導出するしかないんじゃないかなぁとなんとなく思っています.

3. まとめ

今回の記事では「スペクトラムグラフ理論」と言いながらほとんど「スペクトラムグラフ」感が感じられないものだったので, あまりその凄さが通じなかったのかもしれません. しかし実はスペクトラムグラフ理論の技法はグラフの構造上の特徴の情報を得ることが出来ます. 例えば, $(n,k,1,1)=(99,14,1,1)$をパラメータに持つ強正則グラフ(Conwayの問題におけるグラフ)が存在するならば, その最大独立点集合のサイズが高々22であり, 彩色数は5以上である, ということを証明することが出来ます (驚くべき証明があるのですが余白がないので省略します).

そして実際に今回示した手法によってMoore graph や Conway problem に対してある程度までの必要条件を導出することが出来ました. なお今回のConway problemに関する結果については僕は論文でも見たことはなく, (載っている論文がぱっと見見つからないという意味で)新しいものなのかもしれませんが, 教科書に載っている程度の初等的な議論によって得られる結果なので「プロ」の研究者にとっては既知の情報かとは思います. また, 今回の議論は次を参考文献として提示します.

• "Elementary Number Theory, Group Theory and Ramanujan Graphs", Giuliana Davidoff, Mount Holyoke College, Massachusetts Peter Sarnak, (2003)

こちらの本はグラフスペクトル理論の初歩的な部分について解説していて, Ramanujan graph についての話題が書いてあります. 前提知識もあまり必要でなく, 非常に読みやすかったです.

• "Topics in Graph Automorphisms and Reconstruction", Josef Lauri, University of Malta Raffaele Scapellato, Politecnico di Milano, (2016)

こちらの本は algebraic graph theory に関わる話題として automorphism (vertex-transitivityなど)や, グラフ理論における非常に有名な未解決問題: reconstruction conjecture について紹介しています. strongly regular graph, Moore graphについて節が割かれています.