読者です 読者をやめる 読者になる 読者になる

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

数学 Algebraic Topology Computational Topology

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

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

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

{ \displaystyle
\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 } に対し

  1. {
\#  \left\{ \beta^{p+1} > \alpha \mid f(\beta) \leq f(\alpha)  \right\} \leq 1
}
  2. {
\# \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) という。

  1. { \displaystyle
\#  \left\{ \beta^{p+1} > \alpha \mid f(\beta) \leq f(\alpha)  \right\} = 0
}
  2. { \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 } を得てみます。具体的な構成は次です:

 { \displaystyle
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 という概念の説明も含めてまた後日