前の回にグラフの近傍複体という単体的複体からグラフの染色数の下限が与えられ、 これによってクネーザー予想という、クネーザーグラフというグラフの染色数を決定する 予想が解決された、という話を書いていて、今回はこの証明を紹介する、という内容でした。
グラフ$G$の近傍複体$N(G)$というのは、$G$の頂点集合を頂点集合とする単体的複体で、 共通近傍を持つような集合が単体とするような単体的複体です。つまり、次のように定められます。 $$ N(G) = \{ U\subseteq V(G) : \text{$U$は共通近傍頂点を持つ} \}. $$ ここで、$U$の共通近傍頂点とは、$U$のどの頂点とも隣接するような頂点のことです。
クネーザー予想の解決を与えたのは、次の2つの定理です。
定理１：$|N(G)|$が(位相空間として) $(r-2)$-連結なら、$G$は$r$色では彩色できない。
定理２：クネーザーグラフ$KG_{2n+k,n}$の近傍複体$N(KG_{2n+k,n})$は$(k-1)$-連結である。
ここで、クネーザーグラフ$KG_{2n+k,n}$というのは、$\{1,2,\dots,2n+k\}$のサイズ$n$の部分集合を 頂点集合として、2つの集合が共通要素を持たないときに辺を結ぶことで得られるグラフです。 次の図は$KG_{5,2}$（つまり、$n=2$, $k=1$の場合）の例です。
クネーザー予想というのは、このクネーザーグラフ$KG_{2n+k,n}$の染色数が$k+2$であるというものでした。 ここで、$k+2$色用いれば彩色ができるということは比較的簡単に分かり、この予想のポイントは、 $k+1$色では彩色できないということを示すことです。 上記の定理1と定理2が示されれば、クネーザーグラフ$KG_{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年の論文による証明です。
この証明は、おおまかな流れとしては次のような感じになります。
記事ではこの証明の詳細を紹介しました。 この証明は、空間を構成して行く過程や、$\mathbb{Z}_2$-写像の作り方などが少しややこしいのですが、 考え方としてはボルスク-ウラムの定理が働く仕組みをきれいに説明していて、 この意味でとてもよい証明と思います。
八森正泰