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

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

全体の要約：

• 部分集合で閉じた集合族を単体複体(または独立性システム)という. 特にマトロイドは単体複体の特殊ケースである.
• グラフに対して定義されるエクスパンダー性という性質を単体複体に拡張する.
• マトロイドの独立集合族はそのエクスパンダー性を満たす.
• 飛び道具を使うと基上のランダムウォークの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})$は単体複体になりますが, 考えるマトロイドによっては必ずしも純粋になるとは限りません.