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

今回も高次元エクスパンダーに関する記事となります。前回の記事では単体複体の局所エクスパンダー性を定義し、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.