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

今回も高次元エクスパンダーに関する記事となります。前回の記事では単体複体の局所エクスパンダー性を定義し、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$の①正の固有値の個数、②負の固有値の個数、③ゼロ固有値の個数は全て一致する。