第12回、ようやくこれが1年間12回の連載の最後の回に到達しました。 この連載、「雑記帳」ということで、いろいろなことを雑多に紹介していく、としながらも、 第9回～11回のシェラビリティ－関連の3回に向けて、そこで必要な基礎知識を前半のいろいろな 回の中に散りばめておき、この部分の話につなげるという形になっていました。 この山場が前回の11回に終了し、前半に置いていたいろいろな布石も回収が終わってしまい、 じゃぁ最後のこの1回分で何の話を書こうか、というところになったのですが、 最後の1回だけ方向性の離れた話題を持ってくるのもおかしな感じかということで、 後半の話題に近い話として、単体的複体のトポロジー的組合せ論における有名なトピックとして 離散モース理論の紹介をすることにしました。
モース理論は微分可能な多様体上にモース関数という滑らかな関数を与え、 その臨界点の情報のみから多様体のトポロジーを記述する、というようなことになりますが、 離散モース理論はこの仕組みのアナロジーを単体的複体上で行う、というものです。
まず、単体的複体$\Gamma$にモース関数の代わりになる離散モース関数というものを与えるのですが、 これは各単体へ数値を割り当てるという形になります。 （単体的複体が単体の集合で、この単体的複体から実数への関数を考える、ということです。）
ここで、この割り当ては何でもよいわけではなく、離散モース関数の条件を満たさないといけません。
（通常のモース理論でも、モース関数は滑らかな関数なら何でも良いわけではなく、
モース関数としての条件を満たすようにとっていたので、この部分も含めてアナロジーになっています。）
条件は、次の2つの式を満たすことです。
$$ \#\{ \tau\in\Gamma : \sigma\supseteq \tau, \dim \tau=\dim \sigma + 1, f(\tau)>f(\sigma)\} \le 1 $$
$$ \#\{ \tau\in\Gamma : \sigma\subseteq \tau, \dim \tau=\dim \sigma - 1, f(\tau) < f(\sigma)\} \le 1 $$
（$\sigma$や$\tau$という文字は単体的複体$\Gamma$中の単体を表しています。）
だいたいの気持ちとしては、包含関係のある単体同志で次元が1違うところを見たときに、
基本的には大きい次元の単体に割り当てる値が小さい次元の単体の値以上に割り当てたいのだけど、
ある単体$\sigma$に着目してその上下の次元の単体との関係を見たとき、上の次元との間にも下の次元との間にも、
高々1個だけ例外を作ってよい、ということです。
例えば、次の図は離散モース関数の例になっています。
この離散モース関数において、上の2式がいずれも「$=0$」になるような単体$\sigma$、つまり、 上下の次元の単体との間に関数の値の上下関係がすべて保たれるような単体を臨界面といいます。 これがモース理論における臨界点のアナロジーになります。
離散モース関数を与えると、その単体的複体がその離散モース関数における臨界面と同じ個数だけ 各次元の面を持つようなセル複体とホモトピー同値であることが導かれます。 これにより、単体的複体のトポロジーを記述することができる、という形になるわけです。
これは、離散モース関数において上下の次元の単体との関数値の大小関係が例外になっている ところが下図のように低い次元の単体と高い次元の単体のペアになり、 これらを低い次元から高い次元に向けてつぶすような「単純ホモトピー」の操作を行う、 というのが仕組みになっています。 下の図は少し煩雑で分かりにくいですが、上の離散モース関数を用いてつぶしていく過程を絵にしています。 臨界面は$\{b,d\}$と$\{d\}$と$\emptyset$です。これに対応して、最後に得られるものは 辺が1つ、頂点が1つ、そして空集合を持つようなセル複体です。
この、離散モース関数に従って面をつぶしていく矢印の構造は、Chariが記述したモースマッチング というもので説明されます。 下の図はこの単体的複体の面半順序集合のハッセ図ですが、つぶしていくことになる（離散モース関数の条件で 上下関係の例外部分にあたる）ペアのところが、太い矢印になっています。 これらは下から上への矢印です。他の部分は上から下への矢印です。 モースマッチングというのは、面半順序集合のハッセ図の各辺に上から下への向き付けをつけておき、 このハッセ図上のマッチング(互いに共通端点を持たないような辺集合)で、そのマッチングの各辺の向きを 逆転させたものが非巡回的（向き付けに沿ったサイクルを持たない）であるもののことです。 実は、離散モース関数をもとにして得られる下図のような向き付けは必ず非巡回的であることが 簡単に分かります。そして、より重要な事実は、逆にモースマッチングを与えると、そのもとになる ような離散モース関数を構成することができてしまうということです。 つまり、離散モース関数を考えることは、モースマッチングを考えることと本質的に等価なのでした。
このような一連の流れをこの回の記事では紹介したのですが、せっかく「雑記帳」なので、これに関連する 前振りとして、離散モース理論の話に入る前に、一般のグラフにおけるマッチングとその最大化アルゴリズム の話を最初にしました。グラフにおいて最大サイズのマッチングを求めることは計算量クラスとしてはP に入る問題で、交互道（マッチングに入る辺と入らない辺が交互に現われるようなパス）に沿って マッチングの辺を入れ替えることを繰り返す方法で計算することができます。
一方、同様にグラフ上で最大サイズのマッチングを探すという問題でも、条件をつけると 探すことが難しくなってしまうことがある。 そのような例として、交互サイクルを持たないようなマッチングを探す問題を紹介しました。 交互サイクルというのは、マッチングに入る辺と入らない辺が交互に現われるようなサイクルのことで、 ここでは、グラフ上に交互サイクルが生じてはいけないという条件下で、最大サイズのマッチングを探す、 という問題です。この問題は実は、MüllerによってNP-困難であることが示されています。
記事では、グラフのマッチングの話、交互サイクルのないマッチングの話、とした後に 離散モース理論の紹介をしたのですが、この話の流れは、実は、モースマッチングというのは 面半順序上の交互サイクルのないマッチングになるためです。
そうすると、モースマッチングで臨界面の個数が最小になるようなものを探す問題もNP-困難になるのかな、 と言うことになりますが、交互サイクルのないマッチングの話からダイレクトに結論につながるわけでは ありませんが、予想通り、この問題もNP-困難になることが分かっています。 これはJoswigとPfetschによって示されています。
八森正泰