数理解析研究所講究録
第 1922 巻 2014 年 38-49

38
グラフから定まる単体複体の位相について
大阪大学大学院理学研究科
原靖浩 (Yasuhiro Hara)
Graduate school of Sience, Osaka University
洲本実業高校
冨田優次 (Yuji Tomita)
Hyogo Prefectural Sumoto Industrial Senior High School

1序Borsuk-Ulam 型の定理のグラフ理論への応用として，Lov 条 による近傍複体を用いた Kneser
グラフの彩色数に関する定理の証明が知られている ([8]). 近年，グラフの近傍複体に関連し$z$て，位数 2 の巡回群が作用する箱複体やその一般化である $Hom$ 複体などグラフから定まる複体の研究が進んでいて，今後，グラフ理論への応用が期待できる．本稿では，空間に作用する群を位数 2 の巡回群に制限して Borsuk-Ulam の定理に関する不変量を紹介し，箱複体に関するそれらの不変量が彩色数と関係していることについて紹介する．これらの結果は基本
的に [9] に述べられていることであるが，本稿では，Csorba の論文 [2], [3] に書かれた結果をの三角形分割を与えるようなグラフについて近傍複用いた証明を与えている．4 節ではの三角形分割を与え体や箱複体の位相と彩色数などグラフの性質との関係を考察した．
を部分グラフとして含む
るようなグラフは平面グラフであり，頂点が 3 個の完全グラフ$D^{2}$$D^{2}$$K_{3}$

ので彩色数は 3 または 4 であるが，彩色数が 4 であることと，そのグラフの近傍複体が単連結になることが同値であることを証明した．近傍複体や箱複体を考えることがどのようなグラフで有効か (彩色数のよい評価を与えるか) を調べることは応用のために重要と思われるが，ここで考察したグラフは，近傍複体に関する不変量が彩色数のよい評価を与えるようなものであるといえる．

2

Borsuk-Ulam の定理とそれに関係する不変量

位数 2 の巡回群$Z_{2}$の分類空間 $BZ_{2}$ のコホモロジー環は$H^{*}(BZ_{2};Z_{2})\cong Z_{2}[x], \deg(x)=1$である ([11]).

が自由に作用するような位相空間で，$X/Z_{2}$ が弧状連結であるようなものとす
る． $X$ に対して，被覆 $Xarrow X/Z_{2}$ の高さ $h(X)$ を$X$

を$Z_{2}$$h(X)$ $:= \max${$n|\overline{f}^{*}x^{n}\neq 0(\overline{f}:X/Z_{2}arrow BZ_{2}$は classifying maP)}

により定義する．ただし，$X$ が弧状連結でないときには，$X/Z_{2}$ が弧状連結であることから，であり，このときには，$h(X)=0$ と定義することにする．被覆 $Xarrow X/Z_{2}$ に関すが $h(X)$ でる Stiefel-Whitney 類 $w(X)$ を考えると，$w(X)^{n}\neq 0$ を満たすような最大のある．球面に対心作用を考えるとき，$h(S^{n})=n$ である ([11]). 次の命題が成り立つこと$\overline{f}^{*}x=0$$n$$S^{n}$

は容易にわかる．

39
作用がある位相空間とする．$X$ から $Y$ への
命題 2.1. $X$ と $Y$ を自由なするならば，$h(X)\leqq h(Y)$ が成り立つ．
$Z_{2}$$Z_{2}$

写像が存在

写像 $f$ が存在するとき，$f$ から写像 $\overline{f}:X/Z_{2}arrow Y/Z_{2}$ が定まり，証明．$X$ から $Y$ への$Y$ に対する分類写像 $\overline{g}:Y/Z_{2}arrow BZ_{2}$ を考えると，は分類写像である．
$Z_{2}$$\overline{g}\circ\overline{f}:X/Z_{2}arrow BZ_{2}$$(\overline{f}^{*}\circ\overline{g}^{*})x^{n}\neq 0$

ならば$\overline{g}^{*}x^{n}\neq 0$であることより，$h(X)\leqq h(Y)$ が成り立つ．I

命題 2.1 と $h(S^{n})=n$ であることより，$X$ から$h(X)\leqq n$

ら，$X$ のであり， から $X$ への-index と-coindex を$S^{n}$$Z_{2}$$S^{n}$

への$Z_{2}$

写像が存在するとき，写像が存在するとき，$h(X)\geqq n$ である．このことか$Z_{2}$$Z_{2}$$Ind_{Z_{2}}X:=\min\{n|\exists Z_{2}$-map $f:Xarrow S^{n}\}$$coind_{Z_{2}}X:=\max\{n|\exists Z_{2}$-map $f:S^{n}arrow X\}$により定義するとき，coind $z_{2}X\leqq h(X)\leqq Ind_{Z_{2}}X$が成り立つことがわかる．また， -index と$Z_{2}$$Z_{2}$-coindex については，命題 2.1 と同様に次の命題が成り立つ．

命題 2.2. $X$ と $Y$ を自由な

$Z_{2}$

作用がある位相空間とする．$X$ から $Y$ への$Z_{2}$

写像が存在するならば，$Ind_{Z_{2}}X\leqq Ind_{Z_{2}}Y$ および $coind_{Z_{2}}X\leqq coind_{Z_{2}}Y$ が成り立つ．
への写像 $f$ が存在するとき，$k=Ind_{Z_{2}}Y$ とおくと，$Y$ から
証明．$X$ から $Y$ へのへの写像 が存在する．$g\circ f$ は $X$ から写像であり，$Ind_{Z_{2}}X\leqq k=Ind_{Z_{2}}Y$ が$S^{k}$$Z_{2}$$S^{k}$$Z_{2}$$Z_{2}$$g$わかる．

写像 が存在する．
から $X$ への
また，$l=coind_{Z_{2}}X$ とすると，へのら写像であり，$Ind_{Z_{2}}Y\geqq l=Ind_{Z_{2}}X$ がわかる．1$S^{l}$$Y$$Z_{2}$$h$$f\circ h$

は$S^{k}$か$Z_{2}$

次の定理は [10] の定理 1.1 においてホモロジーで書いているものであるが，コホモロジー
でも Gysin-Smith 完全系列を使って同様に証明できる．

作用がある弧状連結な位相空間で， $1\leqq p\leqq m$ に対して作用がある Hausdorﬀ 空間
を自由な$H^{p}(X;Z_{2})=0$ をみたすものとする．また，への写像は存在しで，$H^{m+1}(Y/Z_{2};Z_{2})=0$ を満たすものとする．このとき，$X$ から

命題 2.3.

$X$が自由な$Z_{2}$$Y$$Z_{2}$$Y$$Z_{2}$

ない．
$k\leqq m$のとき $H^{m+1}(S^{k}/Z_{2};Z_{2})=0$ なので，

$Z_{2}$-index について次が成り立つ．

作用がある弧状連結な位相空間で，$1\leqq p\leqq m$ に対し $H^{p}(X;Z_{2})=0$をみたすものとする．このとき，$Ind_{Z_{2}}X\geqq m+1.$

系 2.4. $X$ が自由な

$Z_{2}$

40
実は，系 2.4 の仮定を満たすような $X$ に対しては，Gysin-Smith 完全系列を使うと $h(X)\geqq$$m+1$ であることが示される．このことからも，$Ind_{Z_{2}}X\geqq m+1$ を証明することができる．

このように，$Ind_{Z_{2}}X$ を知るには $h(X)$ を計算するのが有効であるが，$h(X)\neq Ind_{Z_{2}}X$となるような $X$ も存在する．その例を以下に挙げておこう．ここに挙げる例は [2] に書いてある例と同じ考え方でできるものである．

に対心作用を考え，$h:S^{3}arrow S^{2}$ を Hopf map とする．2 つの $D^{4}=\{x\in R^{4}|\Vert x\Vert\leqq 1\}$
で以下のようにつける．
を境界を考え， に 2 つの$S^{2}$$D^{4}$$S^{2}$$S^{3}$$X=S^{2} \bigcup_{h}D^{4}\bigcup_{-h}D^{4}$$-h$ は $h$ に対心点を入れ替える写像を合成したものである．2 つの $D^{4}$に入れ替えるような作用を考えることができて，この作用は自由である．このとき，$h(X)=2$ であることは Gysin-Smith 完全系列を考えることによりわかる．次に，$Ind_{Z_{2}}X$への写から不変な部分空間
であるが，これは 2 にはならない．なぜなら，$X$ のからへの写像 $foh$ を考えるとの境界像 の写像度は ではないので，に拡張することができないからである．この例の $X$の元としてにはならず，これを作用を考えれば，$X$ に$Z_{2}$$Z_{2}$$S^{2}$$Z_{2}$$D^{4}$$0$$f$$S^{3}$$S^{2}$$S^{2}$$Z_{2}$$\pi_{3}(S^{2})$$D^{4}$$0$については，$Ind_{Z_{2}}X=3$ となる．に原また，$h(X)$ と $coind_{Z_{2}}X$ で $h(X)>coind_{Z_{2}}X$ となるような $X$ の例としては，
点対称に埋め込んだ種数が正の偶数であるような有向閉曲面がある．ただし， 作用は原$R^{3}$$Z_{2}$

点対称な点を入れ替えるようなものを考える．これについては，$h(X)=2$ で coindz2 $X=1$である．

3

グラフの近傍複体，箱複体$G=(V, E)$ を単純グラフ (多重辺とループがない) とする．また，$n$を自然数とするとき，$[n]$を表すことにする．$c:Varrow[n]$ が $\{u, v\}\in E$
ならば $c(u)\neq c(v)$ を満たすとき， を彩色という．また，彩色 $c:Varrow[n]$ が存在するような最小のを彩色数といい，$\chi(G)$ により表すことにする．
どの 2 つの頂点も隣接している (辺で結ばれている) グラフを完全グラフとよび，頂点で表すことにする．容易にわかるように $\chi(K_{n})=n$ での個数が 個の完全グラフを
により

$n$

以下の自然数全体の集合 1, 2, . . . ,
$\{$

$n\}$

$c$

$n$

$n$

$K_{n}$

ある．

この章で紹介する近傍複体は，Kneser graph の彩色数の研究において Lov\’asz により定義された ([8]). また，Matousek の著書 [9] にも近傍複体と箱複体についての詳しい解説がある．まずは Kneser graph の定義を述べよう．

Kneser graph $KG_{n,k}(n\geqq 2k)$ の頂点集合$V(KG_{n,k})$は，$V(KG_{n,k})=(\begin{array}{l}[n]k\end{array})$

でになるものが頂点である．また，定義される．つまり， $[n]$ の部分集合で，元の個数がであるとき$A_{2}\subset V(KG_{n,k})$ に対して，$\{A_{1}, A_{2}\}\in E(KG_{n,k})$ であるのはと定める．Lov\’asz が [8] で証明したのは，次の定理である．
$k$$A_{1},$$A_{1}\cap A_{2}=\emptyset$

41
定理 (Lovasz [8]). $\chi(KG_{n,k})=n-2k+2$

この定理で，$\chi(KG_{n,k})\leqq n-2k+2$ を示すのはそれほど難しくない． $c:V(KG_{n,k})arrow$$[n-2k+2]$ を $A\in V(KG_{n,k})(\subset[n])$ に対して，$c(A)= \min\{\min(A), n-2k+2\}$ と定義す
ると，これが彩色になっているからである．$\chi(KG_{n,k})\geqq n-2k+2$ を示すのに Lovasz は近傍複体と Borsuk-Ulam の定理を用いた．
以下ではは 2 つ以上の頂点がある連結なグラフと仮定し，近傍複体の定義について述べよう． の部分集合に対して， の部分集合 $CN(A)$ を
$G$

$V$

$A$

$V$

$CN(A):=\{v|\{v,$ $a\}\in E$ for $\forall a\in A\}(\subset V)$

により定義する．また， の部分集合族 $N(G)$ を$V$$N(G):=\{A\subset V|CN(A)\neq\emptyset, A\neq\emptyset\}$により定義する． $CN$ の定義より，$B\subset A$ ならば $CN(B)\supset CN(A)$ が成り立つので，$A\in N(G)$ かつ $B\subset A(B\neq\emptyset)$

であり，頂点集合は$V$

ならば，$B\in N(G)$ であり，$N(G)$ は単体複体 (抽象複体)と同一視できる．

例．

$arrow$

近傍複体上には，一般には自由な作用がない．Lovasz は近傍複体の細分を考え，その部分複体として自由な作用のある複体を考えた ([8]). ここでは，もう少し簡単に (図形は複雑になるが，定義やその後の定理を導くのが簡単ということ), 以下に定義する箱複体を$Z_{2}$$Z_{2}$

使って考えることにする．
$A_{1},$ $A_{2}\subset V$に対して，$V\cross\{1$ , 2 の部分集合$\}$$A_{1}\cup A_{2}$を$A_{1}\cup A_{2}=A_{1}\cross\{1\}\cup A_{2}\cross\{2\}$により定義する．$V\cross\{1$ , 2$\}$の部分集合族からなる単体複体 $B(G)$ を$B(G):=\{A_{1}\cup A_{2}|A_{1}, A_{2}\subset V, A_{1}\cap A_{2}=\emptyset,$$\{u, v\}\in E$

for$CN(A_{1})\neq\emptyset$$\forall u\in A_{1},$ $\forall v\in A_{2},$or$CN(A_{2})\neq\emptyset$

$\}$

42
により定義する．$T:B(G)arrow B(G)$ を $A_{1}\cup A_{2}\mapsto A_{2}\cup A_{1}$ により定義すると，$T^{2}=id$ であり，$T$ が不動点を持たないことは容易にわかる．

,...,
,...,
の箱複体). $B(K_{n})$ の頂点集合は {1}であり，極大な単体は，$A\cup B=[n],$ $A\cap B=\emptyset,$ $A\neq[n],$ $B\neq[n]$ であるような $[n]$ の部分

例($u\emptyset,$$K_{n}$$\{n\}\cup\emptyset,$ $\emptyset\cup\{1\}$$\{2\}\cup\emptyset$$\emptyset\cup\{n\}$集合 $A,$ $B$ を用いて $A\cup B$ と書かれるものである．
$i$

頂点

に対して

$\{i\}\cup\emptyset$$R^{n}$き $B$の $(0, \ldots, 0, 1 0, \ldots, 0)$を対応させ，$\emptyset\cup\{i\}$に対して$R^{n}$$i\mathfrak{F}\in\exists$の $(0, \ldots, 0, -1,0, \ldots, 0)$ を対応させることにより，$|B(K_{n})|$ は $n$ 次元 cross polytope の境界部分から 2 つの面に$Z_{2}$$[n]\cup\emptyset,$を取り除いたものになる．したがって，$|B(K_{n})|$ は $S^{n-2}$$\emptyset\cup[n]$ホモトピー同値なものである．

以下，$G,$ $H$ を単純グラフとする． $f:V(G)arrow V(H)$ が $\{u, v\}\in E(G)$ であれば常にから $H$ へのグラフ準同型という．グラフ準同$\{f(u), f(v)\}\in E(H)$ を満たすとき， を型を $f:Garrow H$ とも書く．グラフ準同型 $f:Garrow H$ は，単体写像
$f$

$G$

$B(f):B(G)arrow B(H) , A_{1}\cup A_{2}\mapsto f(A_{1})\cup f(A_{2})$写像になっていることに注意しておこう．
を導く．また，この単体写像は
さて，$\chi(G)=n$ であることは，$[n]$ への彩色が存在し，$[n-1]$ への彩色が存在しないとへのグラフ準同型が存在し， から $K_{n-1}$ へのグラいうことであるが，これは， からフ準同型が存在しないということに他ならない．したがって，$\chi(G)=n$ であるとき，彩色よ
ホモトピー同値
写像が誘導され，$|B(K_{n})|$ は $S^{n-2}$ にり $|B(G)|$ から $|B(K_{n})|$ へのなので，$n-2\geqq Ind_{Z_{2}}B(G)$ であることがわかる．したがって，次のことが成り立つ．
$Z_{2}$$G$$G$$K_{n}$$Z_{2}$$Z_{2}$

定理 3.1. $\chi(G)\geqq Ind_{Z_{2}}B(G)+2\geqq h(B(G))+2\geqq coindz_{2}B(G)+2.$

この定理から，$\chi(G)$ を調べるのに $B(G)$ の位相を調べることが有効であることがわかる．しかしながら，$B(G)$ は単体の数が多くて，例えばホモロジーの計算などは大変である．
近傍複体 $N(G)$ の方が単体の数が少なくて見やすいが，$N(G)$ と $B(G)$ について次の命題が成り立つ．

命題 3.2([3]). $|B(G)|$ と $|N(G)|$ はホモトピー同値である．
証明の概略．$\{A_{1}\cup A_{2}\in B(G)|A_{2}=\emptyset\}(\subset B(G))$ と $N(G)$ は単体複体として同型である．
$G$ の頂点集合$V(G)$ をと表し，$V(G)$ のベキ集合から $N$ への写像 を$:= \min\{i_{1}, . . . , i_{k}\}$ により定義する．
$\{v_{1}, .

.

.v_{n}\}$$\alpha$$\alpha(\{v_{i_{1}}, \ldots, v_{i_{k}}\})$$B(G)$の部分集合$\{v_{i_{1}}\cup\emptyset, .

.

.

$\Sigma$

を次を満たすものとして定める :, v_{i_{l}}\cup\emptyset, \emptyset\cup vj_{1},.

.

.

, \emptyset\cup vj_{m}\}\in\Sigma$$\Leftrightarrow\alpha(CN(\{v,., v \not\in\{i_{1}, .

$\sigma:\Sigmaarrow B(G)\backslash \Sigma$

を$\sigma_{\tau}=\tau\cup\{v_{\alpha(\{y_{1},\ldots,y_{m}\})}\cup\emptyset\}$.

.

, il\} (ただし，m\geqq 1 とする)$

により定義するとき，.

43$B(G)\searrow B(G)-\{\tau_{1}, \sigma_{\mathcal{T}1}\}\searrow B(G)-\{\tau_{1}, \sigma_{\mathcal{T}1}, \tau_{2}, \sigma_{\mathcal{T}2}\}\searrow\cdots\searrow N(G)$となるような elementary collapse の列が存在する．これにより，$B(G)$ と $N(G)$ は simple
homotopy 同値であり，$|B(G)|$ と $|N(G)|$ がホモトピー同値であることがわかる .I

この命題より，$|N(G)|$ が -連結であれば，$|B(G)|$ も -連結であり，したがって，定理 3.1
$k$

$k$

と系 2.4 より次のことがわかる．

命題 3.3(Lovasz の不等式 [8]). $N(G)$ が$k$

連結ならば (G) $\geqq k+3.$$\chi$

Lovasz は [8] の中で，ここで説明した方法とは別の方法でこの不等式を導き，Kneser graph$KG_{n,k}$が $(n-2k-1)$ -連結であることを証明することにより，この節の初めの方で紹介した等式 $\chi(KG_{n,k})=n-2k+2$ を証明した．この等式を見ると，Lovasz の不等式や定理 3.1

は彩色数を調べるのにかなり有効に思える．しかし，次のような定理が知られている．
定理 (Erd\"os, Lovasz). 任意の 2 つの整数 $m,$ $n\geqq 2$ に対して，どの閉道も $m$ より大きい
ような

$n$

-彩色グラフが存在する．

どの閉道も 5 より大きければ，近傍複体や箱複体のホモロジー群は 2 次以上では消える．
このとき，$Ind_{Z_{2}}B(G)+2\leqq 3$ であり，近傍複体や箱複体を用いるのは彩色数を調べるのに有効とはいえない．次節で，近傍複体や箱複体を考えるのが有効になるようなグラフについて考察しよう．

4$D^{2}$の三角形分割グラフについての 3 角形分割グラ
2 次元円板 $(D^{2})$ の 3 角形分割の 1 切片になっているようなグラフを$G$$G$の 3 角形において， の頂点がフと呼ぶことにする．また， の 3 角形分割グラフの内部にある頂点と呼ぶことにする．グラフ
分割の境界上にないときには，その頂点をの 3 角形分割グラフ $G$ は平の頂点 の次数とは， に接続する辺の個数のことである．
を部分グラフとして面グラフであり，四色定理 ([1]) より $\chi(G)\leqq 4$ となる．また，$G$ は$D^{2}$$D^{2}$$D^{2}$$D^{2}$$v$$v$$D^{2}$$K_{3}$

含むので，$\chi(G)$ は 3 か 4 である．[12] の定理 19.4 の証明と同様にして次のことがわかる．

の 3 角形分割グラフでは，内部の頂点に奇数次数のものがあれば $\chi(G)=4$ であり，内部の頂点がすべて偶数次数であるか内部の頂点が存在しなければ $\chi(G)=3$ である．

命題 4.1.

$D^{2}$

以下では，$D^{2}$の 3 角形分割グラフ $G$ の近傍複体 $N(G)$ の位相について考えることにしよう．まず，次のことが成り立つ．
命題 4.2. 連結で彩色数が 3 以上のグラフ $G$ の近傍複体 $N(G)$ は連結である．

44
証明．$N(G)$ の 2 つの頂点 $u,$ は $G$ の頂点でもあり， が連結で彩色数が 3 以上のグラフであることから， から への歩道で長さが偶数になるものがある．
なぜなら，まず歩道 $u=a_{0},$ , . . . , $a_{n}=v$ は $G$ の連結性より存在する． が奇数の場
合に，これを利用して長さが偶数の歩道を次のように構成する :彩色数が 3 以上のグラフとする． からへの歩道を考え，奇閉路には奇閉路を持つので，それを , . . . , $b_{2k-1},$
からにもどる歩道は から自身への歩道で，長さが, . . . , $b_{2k-1},$ を 1 周した後に奇数である．このように作った長さが奇数の歩道と，長さが奇数の歩道 $u=a_{0},$ , . . . , $a_{n}=v$
$G$

$v$

$u$

$v$

$n$

$a_{1}$

$u$

$u$

$u$

$b_{1}$$b_{1}$$b_{1}$$b_{1}$$u$$b_{1}$$b_{1}$$a_{1}$をつなげると

$u$

から

$v$

への長さ偶数の歩道が作れる．

さて，長さが偶数の歩道 $u=a0,$ , . . . , $a_{2k}=v$ を考えると，$\{a0, a_{2}\}\subset N(a_{1})$ ,と$N(a_{3})$ , . . . , $\{a_{2k-2}, a_{2k}\}\subset N(a_{2k-1})$ なので，$N(G)$ において，を結ぶ 1-単体の列が存在する．したがって，$N(G)$ は連結である .I$\{a_{2}, a_{4}\}\subset$$a_{1}$$u$$v$の 3 角形分割グラフの近傍複体は命題 4.2 より連結である．次に，$|N(G)|$ の基本群について考える． 頂点の閉路グラフに 1 つの頂点 を加え， と閉路グラフの頂点をすべて結んだ下のようなグラフ耽を車輪と呼ぶ．
$D^{2}$

$v$

$v$

$n$

監の近傍複体のホモトピー型は以下のようになっている．
命題 4.3. $|N(W_{4})|\simeq S^{1}$ であり， が 6 以上の偶数のとき，$|N(W_{n})|\simeq S^{1}\vee S^{2}\vee S^{2}$ . また，
$n$

$n$

が 3 以上の奇数のとき，$|N(W_{n})|\simeq S^{2}.$証明の概略．上の図のように頂点に名前をつける $(1,2, \ldots, n と v)$ . $N(W_{4})$ の極大な単体
2, 4,であり，$|N(W_{4})|\simeq S^{1}$ であることは容易にわかる．
は，{1, 2, 3, 4}, 1, 3,
が 6 以上の偶数のとき $n=2k$ となる自然数をとると，$N(W_{n})$ の極大な単体は，
4, 6, , . . . ,3, 5, , . . . , $\{2k-3, 2k-1, v\},$ $\{2k-1, 1, v\},$ 2, 4,
1, 2, . . . , $2k\},$ 1, 3,$\{2k-2, 2k, v\},$ $\{2k, 2, v\}$ であり，$\{1, 3, . . . , 2k-1\},$ 1, 3,
3, 5, , . . . , $\{2k-3, 2k-1, v\},$$\{2k-1, 1, v\}$ で 1 つとホモトピー同値な部分複体ができ， 2, 4, . . . , $2k\},$ 2, 4, , . . . ,$\{$$v\},$

$\{$

$v\}$

$k$

$n$

$\{$

$\{$

$v\},$

$\{$

$v\}$

$\{$

$\{$

$v\},$$S^{2}$$v\},$

$\{$

$v\}$

$\{$

$v\}$

$v\}$

$\{$

$\{$

とホモトピー同値な部分複体ができて，$\{1, 3, . . . , 2k-1\}$と 2, 4, . . . , $2k\}$ が極大な単体 1, 2, . . . , $2k\}$ の面でつながっている．それ以外に頂点 で 2
つのがつながるから，$|N(W_{n})|\simeq S^{1}\vee S^{2}\vee S^{2}$ となる．
が 3 以上の奇数のとき，$n=2k+1$ となる自然数 をとると，$N(W_{n})$ の極大な単体
3, 5, , . . . , $\{2k-1, 2k+1, v\},$ $\{2k+1, 2, v\},$ 2, 4, , . . . ,は，$\{1, 2, . . . , 2k+1\},$ 1, 3,$\{2k-2, 2k, v\},$ $\{2k, 1, v\}$ であり，$\{1, 2, . . . , 2k+1\}$ をつぶすような写像で $|N(W_{n})|$ とのホモトピー同値写像が作れる．I$\{2k-2, 2k, v\},$ $\{2k, 2, v\}$ で 1 つ$S^{2}$

$v$

$\{$

$\{$

$S^{2}$

$k$

$n$

$\{$

$v\},$

$\{$

$v\}$

$\{$

$v\}$

$S^{2}$

45$W_{n}$の基本群については命題 4.3 でわかるが，一般のの 3 角形分割グラフの近傍複$D^{2}$

体の基本群について次のことが成り立っ．
定理 4.4. $G$ がの 3 角形分割グラフのとき， の内部の頂点で奇数次数のものが 1 つでもあれば $|N(G)|$ は単連結であり， の内部の頂点がすべて偶数次数もしくは内部の頂点が$D^{2}$$G$$G$

存在しなければ $\pi_{1}(|N(G)|)\cong Z.$

証明．内部の頂点に奇数次数のものが 1 つでもあるようなの 3 角形分割グラフはその奇数次数の頂点の次数をに下図の (i) のように頂点と辺を加える操作と (ii) のとして，ように辺を加える操作を何度かすることにより得られる． $((i)$ では と辺が加えが加えられている
られいて，(ii) では辺
また，$(i)arrow(i)arrow(ii)arrow(ii)$ のように続けて同じ操作をしてもよい．)$D^{2}$$n$$W_{n}$$v$$a_{1}v,$$a_{2}v$$a_{1}a_{2}$まず，$D^{2}$の 3 角形分割グラフ $G$ に (i) の操作をしたグラフを $G’$ とすると，$G’$ においてである．このようなとき，[5] の Lemma 5 より，$|N(G’)|\simeq|N(G’-v$$|N(G)|)$ である．もう少し補足しておくと，$N(G)$ と $N(G’)$ の違いはの極大な単体 $CN(a_{1})$と $CN(a_{2})$ が $CN(a_{1})\cup\{v\}$ と $CN(a_{2})\cup\{v\}$ にそれぞれなることだけであり，$CN(a_{1})$ と$N(ao)\supset N(v)$

$G$

はともに

$CN(a_{2})$次に$D^{2}$

基本群が$0$$a_{0}$を含むことを考えれば $N(G’)$ は $N(G)$ に collapse することがわかる．

の 3 角形分割グラフ $G$ に (ii) の操作をしたグラフを $G”$ とするとき $|N(G)|$ のであれば，$|N(G")|$ の基本群も であることを示す．
を上図 (ii) のものとする．$N(G)$ と $N(G”)$ の違いは $CN(a_{1})$ が $CN(a_{1})\cup\{a_{2}\}$$0$$a0,$ $a_{1},$ $a_{2}$になり，$CN(a_{2})$ が $CN(a_{2})\cup\{a_{1}\}$ になったことである (ここで，$CN$ は$G$において考えている).
$|N(G")|$の頂点を基点とする閉道は $|N(G")|$ の 1-skelton の中の閉道とホモトープになるので，1-skelton の中の閉道のみを考える． $|N(G)|$ になく $|N(G")|$ にある閉道は，途中で$|CN(a_{2})\cup\{a_{1}\}|$ または $|CN(a_{1})\cup\{a_{2}\}|$ を通るものである． $|CN(a2)\cup\{a_{1}\}|$ の 1-skelton の中の道で $|CN(a_{2})|$ に入っていないものは，というようなグラフ $G$ でと隣接する頂点$ba_{1}$$a_{2}$を含むような $N(G”)$ の 1-単体を通る．しかしながら，という道はう 2 つの 1-単体をつないだ道と $(端点 b, a_{1} を固定して)$ ホモトープであり，$b$と$ba_{1}$$a_{1}$$ba_{0},a_{0}a_{1}$$ba_{0}$といは $|CN(a_{2})|$の道である．aoal もに aoal を辺とする 3 角形があることから，$|N(G)|$ 内の道になってという道は $|N(G)|$ 内の道に (端点を固定して) ホモトープである．同様いる．つまり，に， $|CN(a_{1})\cup\{a_{2}\}|$ を通る道も $|N(G)|$ 内の道にホモトープであり，$|N(G")|$ の頂点を基点$G$$ba_{1}$46とする閉道は $|N(G)|$ 内の閉道にホモト $-7$ になる．したがって，$|N(G)|$ 基本群がことから，$|N(G")|$ の基本群も

$0$

$0$

である

である．

はその
の 3 角形分割グラフ
内部の頂点に奇数次数のものが 1 つでもあるようなに図 (i) の操作と (ii) の操作を何度かすること
奇数次数の頂点 1 つの次数をとして，により得られることと，$\pi_{1}(|N(W_{n})|)=0$ であることより，$|N(G)|$ が単連結であることがわ$D^{2}$$G$$W_{n}$$n$かる．

の三角形分割グラフ $G$ で $G$ の内部の頂点がすべて偶数次数もしくは内部のに上の (i) と (ii) の操作を頂点が存在しない場合であるが，このときは完全グラフ

次に，$D^{2}$$K_{3}$

何度かして $G$ ができる．(i) ではホモトピー型が変わらない．また， $|N(K_{3})|\approx S^{1}$ で$\pi_{1}(|N(K_{3})|)$ は 1 個の元で生成される，上の (ii) の証明と同様にして，(ii) の操作で基本群の生成元の個数は 1 個のままかそれより少なくなることがわかる． $G$ の内部の頂点がすべて偶数次数もしくは内部の頂点が存在しない場合は $\chi(G)=3$ なので，$\pi_{1}(|N(G)|)=0$ であれば，命題 3.3 に反する．したがって，$\pi_{1}(|N(G)|)$ は $Z$ もしくは $Z/mZ$ である．グラフ準同型 $f:K_{3}arrow G$ および $g:Garrow K_{3}$ が存在して，$g\circ f:K_{3}arrow K_{3}$ は恒等写像なので，$N(g)_{*}\circ N(f)_{*}:\pi_{1}(|N(K_{3})|)arrow\pi_{1}(|N(K_{3})|)$ は恒等写像である．このことから，$\pi_{1}(|N(G)|)=Z$ がわかる．I
命題 4.1 と定理 4.4 の結果から次のことがわかる．
系 4.5.

$D^{2}$の 3 角形分割グラフ $G$ について，$|N(G)|$ が単連結であるための必要十分条件

は $\chi(G)=4$ である．

系 4.5 は， の 3 角形分割グラフでは Loviz の不等式 (命題 3.3) おいて等号が成り立つということに他ならない．また， の 3 角形分割グラフ以外の平面グラフでは Lovasz の$D^{2}$$D^{2}$

不等式が成り立たない例が存在する．下の図の 2 つのグラフでは，近傍複体は単連結とはな
は，彩色数 4 でありながら $Ind_{Z_{2}}B(G_{2})=1$ , つまりらないが彩色数は 4 である．特に$G_{2}$$\chi(G_{2})>Ind_{Z_{2}}B(G_{2})+2$となる例になっている．

$G_{1} G_{2}$
次に，

$G$

が

$D^{2}$の 3 角形分割グラフのときの近傍複体の 2 次以上のホモロジー群についの 3 角形分割において，長さ 3 の閉道とその内部は次の図のいずれかの形をしているものとする．ただし，1 番右のグラフの点線部はそこにいつくかの頂点が縦に並て考えよう．

$D^{2}$

んでいるものとし，それらはそれぞれ 1 つ上，1 つ下の頂点と隣接し，右と左の頂点とも隣接するものとする．

47

また，長さ 4 の閉道とその内部は下図の中のいずれかのものか，それらを折り返してできるものと仮定する．ただし，点線部は上の長さ 3 の閉道の 1 番右のグラフと同様であり，これらは点線の両端の頂点を同一視したグラフ (上図の真ん中の点線がないグラフ) にしてもよい．

このように閉道の形に制限をつけると，次のことが成り立つ．

の 3 角形分割グラフにおいて， の長さ 3 と 4 の閉道が上のようなものしか存在しないき，近傍複体の 2 次以上のホモロジー群について以下が成り立つ．
定理 4.6.

$D^{2}$$G$(1) $P\geqq 3$ では $H_{p}(N(G);Z)=0.$(2)の内部の頂点に奇数次数のものがあるとき，内部の頂点のうち 4 以外の次数をもつ頂点の個数をとすると，$H_{2}(N(G);Z)\cong Z^{2n-1}$$G$(3)の内部の頂点がすべて偶数次数であるとき，内部の頂点のうち 4 以外の次数をもつ頂点の個数をとすると，$H_{2}(N(G)_{1}Z)\cong Z^{2n}$
$G$

$n$

$n$

証明の概略．証明は定理 4.4 の証明の中の (i), (ii) の操作をしたときの変化を考える．(2) の場合，つまりグラフの内部の頂点に奇数次数のものがあるときは，奇数次数の頂点の次数をを考え，(3) の場合は，を考えて，(i), (ii) の操作を繰り返すことによりグとして，ラフを構成する．(i), (ii) の操作で近傍複体における自然な包含写像から誘導される基本群の準同型が同型なので，1 次ホモロジー群は変わらないことに注意しておこう．つまり，(2)のとき $H_{1}(N(G))=0$ , (3) のとき $H_{1}(N(G))\cong Z$ である．ここで，ホモロジー群の係数は$Z$ である．以下も，ホモロジー群の係数は $Z$ とする．
さて，(i), (ii) の操作をしたときの 2 次以上のホモロジー群の変化についてであるが，まず，(i) の操作の前後の近傍複体はホモトピー同値なのでホモロジー群も変わらない．次に(ii) の操作前のグラフを , 操作後を G’ とする．$CN_{G}(a_{1})\cup\{a_{2}\}$ とその辺単体からなる単体複体を Ll(ここで，$CN_{G}$ は $CN$ をで考えたもの), $CN_{G}(a_{2})\cup\{a_{1}\}$ とその辺単体からなる単体複体をとし，$K_{1}=N(G)$ , $K_{2}=L_{1}\cup L_{2}$ とする．このとき，$N(G’)=K_{1}\cup K_{2}$$n$$W_{n}$$K_{3}$$G$$G$$L_{2}$

48であり，$K_{1},$$K_{2}$に Mayer-Vietori 完全系列を考えることにより $N(G’)$ のホモロジー群を計算する．
$K_{1}\cap K_{2}=K_{1}\cap(L_{1}\cup L_{2})=(K_{1}\cap L_{1})\cup(K_{1}\cap L_{2})$$|CN_{G}(a_{1})\cap CN_{G}(a_{2})|$は可縮であることから，$K_{1}\cap L_{1}$で， $|(K_{1}\cap L_{1})\cap(K_{1}\cap L_{2})|=$のホモロジー群がわかれと $K_{1}\cap L_{2}$は $CN_{G}(a_{1})$ が 1 つの単体で，それ以外のホモロジー群を計算できる．
ば，という形になっている．したがって，$H_{p}(K_{1}\cap L_{1})(k\geqq 1)$の単体は，から長さ 2 の歩道がと隣接しの生成元に現れる単体の頂点は， を除くとグラフ上でという辺を含む長さ 4 のあるようなものに制限することができる．これは，G’ の中で，閉道上に存在する頂点ということになる．
でも同様のことがいえて，結局，辺のホモロジー群はわかる．
を含む長さが 4 の閉道のみを考えれば辺を含む長さが 4 の閉道とその内部が上に挙げたもののときに制限すると，の両方に隣接する頂点が新たな内部の頂点になるとき， の次数が 4 以外であれとなる．(2), (3) いずれの場合も，ば， $H_{p}(K_{1}\cap K_{2})$ は $p=1$ で $Z\oplus Z,$ $p\geqq 2$ では可縮であることから，$K_{1}=N(G)$ と $N(G’)$ の 1 次ホモロジー群は自然に同型であり，Mayer-Vitoris 完全系列を考えると $H_{2}(N(G’))\cong H_{2}(N(G))\oplus Z^{2}$ を得る．また，$p\geqq 3$ では$K_{1}\cap L_{1}$$K_{1}\cap K_{2}$$a_{2}\cup\sigma(\sigma\subset CN_{G}(a_{1}))$$a_{2}$$a_{1}$$a_{2}$$a_{1}a_{2}$$K_{1}\cap L_{2}$$a_{1}a_{2}$$K_{1}\cap K_{2}$$a_{1},$$a_{1}a_{2}$$a0$$a_{2}$$a_{0}$$0$$|K_{2}|$$H_{p}(N(G’))=H_{p}(N(G))=0$ である．
$a_{0}$の次数が 4 のときには，$H_{p}(K_{1}\cap K_{2})$ は $p=0$ 以外では， となり，このときはすべて$0$の $p$ で $H_{p}(N(G’))\cong H_{p}(N(G))$ である．

以上から，(2), (3) いずれの場合も，(ii) の操作を 1 回するとき，次数 4 以外の内点が増え
れば 2 次ホモロジー群のランクが 2 つ増え，それ以外にホモロジー群の変化はない．(2) の場( は奇数) に (i),(ii) の操作を繰
合 (グラフの内部の頂点に奇数次数のものがあるとき),
り返してグラフを構成し，(3) の場合は， に (i),(ii) の操作を繰り返してグラフを構成する$W_{n}$$n$$K_{3}$

が，$|N(W_{n})|\simeq S^{2}$ ( は奇数), $|N(K_{3})|\simeq S^{1}$ であることより定理の結論を得る．I$n$は奇数次数の内部の頂点があり，4 以外の次数をもつ内部の頂点は 4 個だか
は内部の頂点はすべて次数が偶数で，4 以外の次数をら，(2) よりもつ内部の頂点は 2 個だから，(3) より $H_{2}(N(G_{4});Z)\cong Z^{4}.$例．下図の$G_{3}$$H_{2}(N(G_{3});Z)\cong Z^{7}.$$G_{4}$$G_{3} G_{4}$定理 4.6 の長さ 3 と 4 の閉道の形に関する仮定については，ここで与えたたものは強いもは内部の頂点に次数 4のであるが，制限を全くなくすことはできない．例えば，次の図の以外の頂点が 3 個あるが $H_{2}(N(G_{5});Z)\cong Z$ であり， では内部の頂点に次数 4 以外の頂
$G_{5}$$G_{6}$

点は 2 個であるが $H_{2}(N(G_{6});Z)\cong Z^{5}$ である．

49

$o$

$0$

$G_{5} G_{6}$References[1] K. Appel, W. Haken, Every planar graph map is four colourable, Bull. Amer. Math.
Soc. 82 (1976) 711-712.
[2] P. Csorba, Homotopy types of box complexes, Combinatoica. 27(2007), 669-682.
[3] P. Csorba, On the simple-homotopy types of graph complexes and their simple-universality, Canad. Math. Bull. 51 (2008), 535-544.
$Z_{2}$$Z_{2}$[4] P. Csorba, Fold and Mycielskian on homomorphism complexes, Contrib. Discrete
Math. 3 (2008), 1-8.
[5] P. Csorba, Homotopy types of box complexes of chordal graphs, European J. Combin.
31(2010), 861-866.
[6] P. Erd\"os, Graph theory and probability. II. Canad. J. Math. 13(1961), 346-352.

[7] L. Lovasz, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar.
19(1968), 59-67.
[8] L. Lov\’asz, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory
Ser. A25 (1978) 319-324.

[9] J. Matou\v{s}ek, Using the Borsuk-Ulam theorem, Springer, Berlin(2003).

[10] 長崎生光，川上智博，原靖浩，牛瀧文宏，The Smith homology and a generalized BorsukUlam theorem, 京大数理解析研究所講究録 1670 換群論の新たな展開 2009 年，34-39[11] 中岡稔，不動点定理とその周辺，岩波書店，1997 年[12] R. . Wilson (西関隆夫，西関裕子 共訳), グラフ理論入門 (原書第 4 版),$J$

2001 年

近代科学社，