HEXの定理(2)
この記事は以下の記事の続きです:
fibonacci-freak.hatenablog.com
さて、前回はHEXの定理とBrouwerの不動点定理が実は同値であるということを紹介しました。今回はその証明を書こうと思います。それぞれのステートメントを確認しておきましょう。
証明のための第一歩はHEXの定理の次のような言い換えです。
(1)上下の辺を結ぶ道で赤い頂点からなるもの。
(2)左右の辺を結ぶ道で青い頂点からなるもの。
HEXの盤面をそのままグラフに直せば、これがHEXの定理と同値であることがわかります。
それでは不動点定理との同値性を証明しましょう。
HEXの定理不動点定理.
に不動点が存在しないと仮定する。は上で最小値を持つのでそれをとする。また上図のグラフを、上下左右の辺がの上下左右の辺上に来るように内に配置する。このときグラフ上の任意の点についてによる座標, 座標の変化のいずれかは以上なので、前者なら赤に、後者なら青に塗る。両方を満たす場合はどちらに塗ってもよい。上の命題より上下の辺を結ぶ赤い頂点からなる道があるとしても一般性を失わない。
さらにこの道上の頂点を、により座標が以上減少するならば白、増加するならば黒で塗り分ける。道の上端の点は白、下端の点は黒なので、道中の連続する2点で色が異なるものが存在する。を十分大きくとればは任意に小さくでき、かつとできる。これはの一様連続性に反する。
不動点定理HEXの定理.
上と同様ににを埋め込む。命題の(1)(2)いずれも成立しない塗り分けがあったとすると、頂点集合には以下の4つの交わらない部分集合が存在する。
上の辺からの赤い道がある赤い頂点
に属さない赤い頂点
左の辺からの青い道がある青い頂点
に属さない青い頂点
そして十分小さいをとり、(はの頂点集合を表す)を以下のように定める。
ただし仮定からの像はに入ることに注意する。
を小三角形ごとに線形に補間することで連続写像が得られる。不動点定理よりの不動点が存在する。を内部に含むの小三角形の頂点を取ると、の凸包は原点を含むので、これらの頂点はのうち相異なる3つに属する。がそれぞれに属するとしても一般性を失わない。しかしは辺で結ばれているからは上の辺からの赤い道があることになりに矛盾する。
組み合わせ論と位相幾何の間のアナロジーは多々ありますが、このように綺麗に同値になる例は少ないように思います。