組合せ数学の雑記帳 第7回

「ボルスク-ウラムの定理とグラフの彩色」

前の回にグラフの近傍複体という単体的複体からグラフの染色数の下限が与えられ、 これによってクネーザー予想という、クネーザーグラフというグラフの染色数を決定する 予想が解決された、という話を書いていて、今回はこの証明を紹介する、という内容でした。

グラフ$G$の近傍複体$N(G)$というのは、$G$の頂点集合を頂点集合とする単体的複体で、 共通近傍を持つような集合が単体とするような単体的複体です。つまり、次のように定められます。 $$N(G)=\{U\subseteq V(G):U\text{は共通近傍頂点を持つ}\}.$$ ここで、$U$の共通近傍頂点とは、$U$のどの頂点とも隣接するような頂点のことです。

クネーザー予想の解決を与えたのは、次の2つの定理です。

定理１：$|N(G)|$が(位相空間として) $(r-2)$-連結なら、$G$は$r$色では彩色できない。

定理２：クネーザーグラフ$K{G}_{2n+k,n}$の近傍複体$N(K{G}_{2n+k,n})$は$(k-1)$-連結である。

ここで、クネーザーグラフ$K{G}_{2n+k,n}$というのは、$\{1,2,\dots ,2n+k\}$のサイズ$n$の部分集合を 頂点集合として、2つの集合が共通要素を持たないときに辺を結ぶことで得られるグラフです。 次の図は$K{G}_{5,2}$（つまり、$n=2$, $k=1$の場合）の例です。

クネーザー予想というのは、このクネーザーグラフ$K{G}_{2n+k,n}$の染色数が$k+2$であるというものでした。 ここで、$k+2$色用いれば彩色ができるということは比較的簡単に分かり、この予想のポイントは、 $k+1$色では彩色できないということを示すことです。 上記の定理1と定理2が示されれば、クネーザーグラフ$K{G}_{2n+k,n}$を$k+1$色で彩色できない ことが分かり、予想が解決されるわけです。

今回の記事で解説したのは、定理１の証明でした。（定理２の証明は第9回で紹介。）

この定理１の証明の鍵となるのが、タイトルにある、ボルスク-ウラムの定理です。 ボルスク-ウラムの定理にはいろいろな形の等価な言明がある（このことは第8回で紹介しました）のですが、 ここで使われるのは次の形の定理です。

定理３（ボルスク-ウラムの定理）：
${\mathbb{Z}}_2$-空間$(T,{\nu }_T)$において$T$が$d$-連結であるとき、 $(T,{\nu }_T)$から$(S^d,{\nu }_{S^d})$への${\mathbb{Z}}_2$-写像は存在しない。

この定理中に出てくる「${\mathbb{Z}}_2$-空間$(T,{\nu }_T)$」というのは、 自由${\mathbb{Z}}_2$-作用${\nu }_T$を備えているような位相空間$T$のこと、 ${\mathbb{Z}}_2$-作用というのは2回作用させると元に戻るような作用のことで、 この作用が自由であるというのは、不動点を持たない、ということです。 また、${\mathbb{Z}}_2$-写像とは、${\mathbb{Z}}_2$-作用の構造を保ったまま ${\mathbb{Z}}_2$-空間から別の${\mathbb{Z}}_2$-空間へ写す連続写像のことです。

標準的な${\mathbb{Z}}_2$-空間が$d$次元球面$S^d$において各点を対極点に移す 写像を${\mathbb{Z}}_2$作用${\nu }_{S^d}$とする$({\mathbb{Z}}_2,{\nu }_{S^d})$で、 このボルスク-ウラムの定理は、ある${\mathbb{Z}}_2$-空間から 標準的な${\mathbb{Z}}_2$-空間である球面上への${\mathbb{Z}}_2$-写像の有無に関して、、 $d$-連結性がその障害になる、という主張です。

このクネーザー予想の解決は、Lovászが1978年に解決した後、別証明がいろいろ与えられているのですが、 ここで紹介したのは、Walkerの1983年の論文による証明です。

この証明は、おおまかな流れとしては次のような感じになります。

• $N(G)$からうまく${\mathbb{Z}}_2$-作用を持つ空間を作る。
• グラフ$G,H$の間にグラフ準同型$G\to H$があるとき、 $N(G)$から作った空間から$N(H)$から作った空間への${\mathbb{Z}}_2$-写像が作れることを示す。
• 完全グラフ$K_r$に対して、$N(K_r)$から作られる空間は$(r-2)$次元球面の${\mathbb{Z}}_2$-空間になる。

記事ではこの証明の詳細を紹介しました。 この証明は、空間を構成して行く過程や、${\mathbb{Z}}_2$-写像の作り方などが少しややこしいのですが、 考え方としてはボルスク-ウラムの定理が働く仕組みをきれいに説明していて、 この意味でとてもよい証明と思います。

戻る