tkenichi の日記

毒舌皮肉系恥さらし日記

Helly の定理

f:id:tkenichi:20121110103015j:plain

離散幾何の有名な定理で Helly の定理というのがある。

 \bf{R}^{n} の m 個の凸集合について、任意の n+1 個の部分族の交わりが非空ならば、すべての交わりも非空である。逆は自明なので、以下が言える。

Helly の定理
 \mathcal{F} = \{ U \subset \bf{R}^{n} | \mbox{convex} \} ; |\mathcal{F}| = m \geq n+1

 \forall \mathcal{F'} \subset \mathcal{F} \ ;\ \cap_{U \in \mathcal{F'}} U \neq \emptyset \ , \ |\mathcal{F'}| = n+1
 \Leftrightarrow
 \cap_{U \in \mathcal{F}} U \neq \emptyset

この証明をいくつか探しているうちに、Homology を利用したもの(というよりも、この定理を Homology 理論の言葉に翻訳したものと言ったほうがいいかもしれない)があったので(証明はかなりいい加減だが)紹介しよう。初等幾何と、トポロジーをつなげるよい例だと思う。

まずは開被覆(Open Cover)に対する Nerve の定義から。

Nerve の定義
開集合の族  \mathcal{F} が与えられているとする。添え字集合を  I とする。
 \mathcal{F} の Nerve  \mathcal{N} とは、添え字集合の部分集合で、その部分族の交わりが存在するものをいう。空集合は Nerve に含めるとする。
 J \in \mathcal{N} \Leftrightarrow J = \emptyset \mbox{ or} J \subset I \ , \cap_{i \in J} U_{i} \neq \emptyset

Nerve から自然に複体 (Complex) が定義できる。k 次の複体は、k+1 個の添え字の部分集合で、順序を考慮したものが生成する加群で(添え字の置換で置換の符号倍で作用する)、境界作用素は、添え字をひとつ除いたものの交代和である。

 C^{k}(\mathcal{N}) = \{ (i_0,i_1,...,i_k) ; \{i_j\} \ in \mathcal{N} \}
 d : (i_0,i_1,...,i_k) \mapsto (i_1,...,i_k) - (i_0,i_2,...,i_k) + \cdots + (-1)^k (i_0,i_1,...,i_{(k-1)})

これから定義されるホモロジー群について、Nerve Lemma が成り立つ。

Nerve の交わりのすべてが空集合か可縮であるとき、Nerve から定義される複体のホモロジー群と、和集合  \cup_{U \in \mathcal{N}} Uホモロジー群には自然な同型がある。

Helly の定理の仮定を満たす場合、Nerve Lemma の仮定を満たす(凸な開集合の交わりは空集合か可縮)ことに注意する。

ホモロジー論から(Alexander duality を使う) X \subset \bf{R}^n について、 H_{q}(X) = \{0\} \  q \geq n
が成り立つ。

以下では  X = \cup_{U \in \mathcal{F}} U とする。Helly の定理の仮定を満たすとする。
Nerve から定義される複体を考えると、
 C^{n} は n+1 個の添え字の部分集合すべてから生成される可群になる。一方、 H_{n}(X) = \{0\} であるから、
境界作用素の Kernel(  d : C^{n} \to C^{n-1} ) は Image(  d: C^{n+1} \to C^{n} ) と一致する。
Kernel を書き下すことで、 C^{n+1} は n+2 個の添え字の部分集合すべてから生成される可群になることがわかる。
以下、帰納的な議論で  C^{m-1} が m 個の添え字の集合から生成される可群になる、すなわち  \cap_{U \in \mathcal{F}} U \neq \emptyset がわかる。

結局は、Nerve から定義されるホモロジー群について  H_{q}(X) = \{0\} \  q \geq n が Helly の定理をホモロジー的に言い換えたものだと解釈してよいのだと思う。