s.t. は such that ではありません

幾何学寄り

離散 Morse 理論紹介~その１~

数学 Algebraic Topology Computational Topology

これは数学 Advent Calendar 2016 18 日目の記事です。遅れまくってｽﾐﾏｾﾝｽﾐﾏｾﾝｽﾐﾏｾﾝｽﾐﾏｾﾝ。。。 17 日目は snuffkin さんによるはじめての圏論でした。19 日目は kobae964 さんによるモナドTipsについてです。

離散数学、最近ではコンピュータグラフィック、データ分析でも見ることがある Discrete Morse 理論を軽く眺めてみようと思います。*1 多様体に対しての morse 理論は今回は解説しませんが、詳細については例えば [Milnor] などを参考にしてください。

離散 Morse 理論では、与えられた CW 複体の homotopy 型を変えずに cell の個数を減らすことを目標とします。cell の数が減るということは、境界準同型

$\partial : M_n(X) \to M_{n-1}(X)$

を行列表示した際の行列のサイズが小さくなることを表し、データの位相的な性質を求める際の計算量が削減できるわけです。また、具体的な cycle, cocycle の計算も可能になったりと、みんな happy(^^)

CW 複体の正確な定義は述べませんが、胞体複体であってよい位相を持つものと考えておいてください。*2。

簡単のために以下では対象としては単体複体とします。(あくまでも対象は。最終的に出来上がるものは CW 複体)。

以下、 K と書いたら単体複体とします。

Morse 関数と臨界点

まずは定義を見てください。

Def(離散 morse 関数)

${ \displaystyle f: K \to \mathbb{R} }$ は任意の p-単体 ${ \alpha^p \in K }$ に対し

${ \# \left\{ \beta^{p+1} > \alpha \mid f(\beta) \leq f(\alpha) \right\} \leq 1 }$
${ \# \left\{ \gamma^{p-1} \lt \alpha \mid f(\gamma) \geq f(\alpha) \right\} \leq 1 }$

の 2 条件が成立するときに Morse 関数という。 ${ \Box }$

Def(critical)

${ f: K \to \mathbb{R} }$ を morse 関数とする。 ${ \alpha^{p} \in K }$ はつぎを満たすとき p-次の critical simplex(CW 複体のときは critical cell) という。

${ \displaystyle \# \left\{ \beta^{p+1} > \alpha \mid f(\beta) \leq f(\alpha) \right\} = 0 }$
${ \displaystyle \# \left\{ \gamma^{p-1} \lt \alpha \mid f(\gamma) \geq f(\alpha) \right\} = 0 }$

K の critical な p-単体の個数を ${ m_p }$ と書くことにする。

例：
f:id:simizut22:20161225130018j:plain

左は Morse 関数ではありません。0 の値を振ってある edge で上の条件 2 が、5 の値を振っている点で条件 1 が崩れているのがわかります。
一方、右は morse 関数の例になっています。その critical 単体は 0 の値を振ってある頂点と 5 の値を振ってある edge です。 ${ \Box }$

例：
単体複体 K 上の関数 f を各単体 ${ \sigma }$ に対し、その次元を対応させる関数：

${ f(\sigma) = \dim\sigma }$

とすると、これは morse 関数になり、全ての単体を critical simplex としてもつ。 ${ \Box }$

定義の妥当性

この定義、どういうことを考えているのでしょうか。 2 次元の曲面で、指数が 1 の臨界点を持つものを考えます。(ここでいう臨界点や指数は可微分の意味です)いわゆる hyperbolic point です。下の図での原点が対応する点です。

f:id:simizut22:20161225151827p:plain

さて、可微分の場合の morse 関数ではこの 0 よりも少し小さいところから、稜線をたどることで 1 handle を図形に張り合わせます。

その稜線が離散における critical な単体に対応するわけです。端点にいくほど値が小さくなり、face の方向に進むと値が大きくなります。

今日の Main Theorem

さて、Morse 関数があると、その臨界点から多様体の分解がえられました。離散の場合でも同様の結果が言えます。

Thm
K を単体複体で f を K 上の morse 関数とする。このとき K は p 次元のセルを ${ m_p }$ 個持つ CW 複体と homotopy 同値 ${ \Box }$

可微分の場合と同様、weak(および strong) morse 不等式も成立します。

Cor(Weak Morse Inequality)

K を単体複体で f を K 上の離散 morse 関数とする。このとき
${ m_p \geq \beta_p(K) }$

ここで、 ${ \beta_p }$ は K の p-次 betti 数。
とくに
${ \displaystyle \chi(K) = \sum_{p = 0}^{\dim(K)}(-1)^{p}m_p }$

Cor(Strong Morse Inequality)

K を単体複体で f を K 上の離散 morse 関数とする。各 p に大して次の Strong Morse 不等式が成立する

${ m_p - m_{p-1} + \ldots + (-1)^p m_0 \geq \beta_p - \beta_{p-1} + \ldots + (-1)^p \beta_0 }$

計算例

さて、先の定理からなにやら離散 Morse 理論が単体複体の homotopy type を計算するのに使えそうな気がしてきました。最後に一つの例を紹介します。

非連結グラフのなす複体

${N_n}$ を完全グラフ ${ K_n }$ の spanning subgraph、すなわち全ての頂点を持つ subgraph、のうちで非連結なものの集合とします。

${ G_1, G_2 }$ を ${ K_n }$ の spanning-subgraph とします。もし ${ G_1 \subset G_2 }$ かつ ${ G_2 \in N_n }$ とすると、 ${ G_1 \in N_n }$ が成立します。こういう性質を単調減少性と言います。

一般に単調現象なグラフ不変量があると、単体複体を構成することができます。今日は ${ N\_n }$ に対し、単体複体 ${ X_n }$ を得てみます。具体的な構成は次です：

$G \in N_n$ が k-単体 ${ \Leftrightarrow }$ G は k+1 個辺を持つ

先の、単調性からこれが単体複体であることがわかり、k-単体 G の各 face は non trivial な spanning subgraph になっています。

この ${ X_n }$ は次の homotopy 型を持つことが discrete morse theory を用いて示されています。

定理

${X_n}$ は ${ (n-1)! }$ 個の (n-3)球面のウェッジ和とホモトピー同値。

証明は、morse 関数を構成することによります。*3

最後の例と関連して、1-連結グラフ、2-連結グラフの cohomology を、そしてその具体的な生成元を求めることも可能ですが、それは Vassiliev による finite type knot invariant の構成と関連してきますが、それはまた後日。

[Milnor] Milnor, John (1963). Morse Theory. Princeton University Press.

*1:今日紹介するのは Forman による

*2:有限部分複体による被覆に関する弱位相を持っています

*3:morse 関数の構成に関しては、Gradient Vector Field という概念の説明も含めてまた後日