高次元エクスパンダー: 局所エクスパンダー性の定義と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.