108

数理解析研究所講究録
第2060巻 2018年 108-117

Group Actions on Hom Complexes
大阪大学理学研究科

小路史朗

Shiro Shoji
Gruduate School of Science, Osaka University§1. はじめに(V, E) を有限単純グラフとする. c : V \rightarrow \{1, \cdots , n\} が n ‐彩色であるとは,uv \in E ならば c(u) \neq c(v) を満たすときをいう. n‐彩色が存在するような最小の n\in \mathbb{Z} を G の彩色数といい $\chi$(G) で表す. $\chi$(\mathrm{G}) は整数値のグラフ不変量である.
$\chi$(G) を求める問題を graph coloring problem という graph coloring problem はグG=

ラフ理論においてよく研究されている古典的な問題である.この問題を解くには定義から下からの評価が重要になってくるが、これを求めるために代数トポロジーが応用された.

本稿では,Lovasz によって定義された近傍複体と \mathrm{H}\mathrm{o}\mathrm{m} 複体を紹介する.これらの位相的性質は,与えられたグラフの彩色数と密接に関係している.§2で近傍複体を用いた Kneser conjecture の証明を与え,近傍複体が graph coloring problem を解くことに有効であることをみる.Kneser conjecture はグラフ理論の予想であったが,純粋なグラフ理論や組み合わせ論の手法では証明できず,代数トポロジーを用いて初めて証明された興味深い予想である.また,Kneser graph の近傍複体のホモトピー型についても触れる.§3では, \mathrm{H}\mathrm{o}\mathrm{m} 複体とそれについてのいくつかの性質を紹介し,§4で具体的に \mathrm{H}\mathrm{o}\mathrm{m} 複体の群作用がどのように振舞うかを考察する.

§2. 近傍複体と Kneser conjecture
このセクションでは Kneser graph と呼ばれるグラフの彩色数に関する予想 (Kneser
conjecture) とそれを解くカギとなった近傍複体を紹介する.また,Kneser graph の近傍複体のホモトピー型についても述べる.まずは,Kneser graph を定義しよう.

定義1整数 n,k が k \geq 1, \geq 2k を満たすとする.頂点集合を (^{\{1,\cdot\cdot,n\}}k ) :=\{ \subset\{1, \cdots , n\} | \# u=k \} とし, u, v\in (^{\{1,\cdots,n\}}k) が u\cap v=\emptyset を満たすとき と を辺で
u

n

u

v

結ぶ.このようにして得られる有限単純グラフをKneser graph といい, \mathrm{K}\mathrm{G}_{n,k} と表す.

定義から容易に分かるように, k= 1 のとき \mathrm{K}\mathrm{G}_{n,1} は完全グラフ K_{n} になる.また, \mathrm{K}\mathrm{G}_{5,2} はPetersen graph になる.

109

Kneser graph KG廊の彩色数について考察してみよう. : V(\mathrm{K}\mathrm{G}_{n,k})= (^{\{1,\cdots n\}}k\rangle ) \rightarrowc\{1, , n-2k+2\} を

c(u) :=\displaystyle \min\{\min\{x\in u\}, n-2k+2\}と定めると,この c は (n-2k+2) ‐彩色になっている.よって, $\chi$(\mathrm{K}\mathrm{G}_{n,k})\leq n-2k+2が分かる.1955年に Kneser がこの両者は実は等しいのではないかと予想し (Kneser

conjecture), 1978年に \mathrm{L} 誌zló Lovasz が証明した :定理2 (Kneser, Lovász) $\chi$(\mathrm{K}\mathrm{G}_{n_{:}k})=n-2k+2.
これを証明するために,Lovaszが導入した近傍複体の定義とその位相と彩色数の関係を述べる.

定義3 G=(V, E) を有限単純グラフとする.頂点集合が Vで,共通近傍をもつ Vの部分集合を単体とするような単体複体 \mathrm{N}(G) を近傍複体という.ここで A \subset Vの共通近傍とは,任意の a\in A と隣接するようなVの元のことである.

例えば, K_{n} を完全グラフとすると, N(K_{n}) は標準 (n-1) ‐単体 \triangle_{n-1} のboundary
complex となる.

定理4 (Lovász, 1978, [1]) 任意の有限単純グラフ G に対して, |\mathrm{N}(G)| が尾連結,すなわち任意の l\in \{-1, \cdots , k\} に対して1次元球面 S^{l} から |N(G)| への連続写像
が常に l+1 次元円板 D^{l+1} へ拡張できれば, $\chi$(G) \geq k+3 が成り立つ,

証明の概略.まず,次の3条件を満たすような \mathrm{N}(\mathrm{G}) の1回の重心細分 \mathrm{s}\mathrm{d}\mathrm{N}(\mathrm{G}) の\mathb {Z}_{2} ‐部分複体 \mathrm{L}(G) が存在する (具体的に構成できる):(1) |L(G)| は |\mathrm{N}(G)| と同じホモトピー型をもつ.

(2) \mathb {Z}_{2} ‐同相 $\varphi$ : |L(K_{n})|\rightarrow S^{n-2} が存在する.

(3) 任意のグラフ準同型 f : G\rightarrow H は, \mathb {Z}_{2} ‐写像 L(f) : |L(G)| \rightarrow |L(\mathrm{H})| を誘導する.

$\chi$(G) =m とするとグラフ準同型 f : G\rightarrow K_{m} が存在する. |N(G)| が k ‐連結なので, L(G) の性質 (1) より |L(G)| も k ‐連結である.このとき,簡単な障害理論より\mathb {Z}_{2} ‐写像 $\psi$ : S^{k+1} \rightarrow |L(G)| が存在することがわかる. L(G) の性質 (2), (3) より次の \mathb {Z}_{2} ‐写像の系列を得る :S^{k+1}\rightarrow^{ $\psi$}|L(G)| \rightarrow^{|L(f)|} |L(K_{m})| \rightarrow^{ $\varphi$}S^{m-2}.
Borsuk‐Ulam の定理より k+1 \leq m-2 , すなわち m\geq k+3 を得る.口110

命題5 |N(\mathrm{K}\mathrm{G}_{n,k})| は S^{n-2k} のwedge sum とホモトピー同値になる.

証明の概略. F(N(\mathrm{K}\mathrm{G}_{n,k})) で N(\mathrm{K}\mathrm{G}_{n,k}) のface poset を表すことにする.順序集合
B_{n,k} を

B_{n,k}= \{ S\subset\{1, \cdots , n\} | k\leq\# S\leq n-k \}で定義する. \triangle(F(N(\mathrm{K}\mathrm{G}_{n,k}))) , \triangle(B_{n,k}) でそれぞれの順序複体を表すことにすると,|N(\mathrm{K}\mathrm{G}_{n,k})| =|\triangle(F(N(\mathrm{K}\mathrm{G}_{n,k})))| と |\triangle(B_{n,k})| は同じホモトピー型を持つことが示される. B_{n,k} はshellable poset ゆえ, |\triangle(B_{n,k})| は S^{n-2k} のwedge sum とホモトピー同値になる

口

命題5より |N(\mathrm{K}\mathrm{G}_{n,k})| は (n-2k-1) ‐連結である.よって定理4より, $\chi$(\mathrm{K}\mathrm{G}_{n,k}) \geqn-2k+2 が得られる.これで Kneser conjecture(定理2) が証明された.

ところで,命題5において, |N(\mathrm{K}\mathrm{G}_{n,k})| とホモトピー同値になる S^{n-2k} のwedge
sum を構成する S^{n-2k} の個数を f_{n,k} とする,すなわち |N(\mathrm{K}\mathrm{G}_{n,k})| \simeq S^{n-2k} とする. f_{n,k} の値は一般には知られていなかったが,筆者は f_{n,k} の値を綺麗な形ではないが求めた :定理6 |N(\mathrm{K}\mathrm{G}_{n,k})| \simeq S^{n-2k} とすると,

f_{n,k}=\displayst le\sum_{0\leqp,q\leqk-1}(-1)^{p+q}\left(\begin{ar y}{l n\ p \end{ar y}\right)\left(\begin{ar y}{l n-p\ q \end{ar y}\right)となる.

証明の方針. i=\{1, \cdots , n\} に対して, N(\mathrm{K}\mathrm{G}_{n,k}) の部分複体 A_{i} を

A_{i}=\{A\in N(\mathrm{K}\mathrm{G}_{n,k}) |\forall a\in A, i\not\in a\}と定義すると,S^{n-2k} \simeq |N(\mathrm{K}\mathrm{G}_{n,k})|, n-k に対して
\displaystyle \bigcup_{i=1}^{n}|A_{i}|, j k,
|A_{i_{1}}|\cap\cdots\cap|A_{i_{J}}| は可縮, j\geq n-k+1 に対して |A_{i_{1} |\cap\cdots\cap|A_{i_{\mathcal{J} }|=\emptyset となる.よって,inclusion‐exclusion principle より A_{i} たちが互いに同型であることに注意する==\cdotsと,オイラー数 e() に関する等式(*)=

1+(-1)^{n}f_{n,k}\left(\begin{ar ay}{l n\ 1 \end{ar ay}\right)e(|A_{1}|)- \left(\begin{ar ay}{l} n\ 2 \end{ar ay}\right)e(|A_{1}|\cap|A_{2}|)+\cdots+(-1)^{k}\left(\begin{ar ay}{l } & n\ k & -1 \end{ar ay}\right)e(|A_{1}|\cap\cdots\cap|A_{k-1}|)+(-1)^{k+1}\left(\begin{ar ay}{l n\ k \end{ar ay}\right) +\cdots+(-1)^{n-k+1}\left(\begin{ar ay}{l} n\ n-k \end{ar ay}\right)

111を得る.ここで, |A_{1}| =(|A_{1}|\cap|A_{2}|)\cup(|A_{1}|\cap|A_{3}|)\cup\cdots\cup(|A_{1}|\cap|A_{n}|) なので,再びinclusion‐exclusion principle より, e(|A_{\mathrm{i}}|) は e(|A_{\mathrm{i}}|\cap|A_{2}|) ,, e(|A_{\mathrm{i}}|\cap\cdots\cap|A_{k-1}|)を用いて次のように表すことができる:

e(|A_{1}|)=\left(\begin{ar ay}{l } n & -1\ & 1 \end{ar ay}\right)e(|A_{1}|\cap|A_{2}|)-\cdots+(-1)^{k+1}\left(\begin{ar ay}{l} n-1\ k-2 \end{ar ay}\right)e(|A_{1}|\cap\cdots\cap|A_{k-1}|)+(-1)\left(\begin{ar y}{l n&-1\ k&-1 \end{ar y}\right) +\cdots+(-1)^{n-k}\left(\begin{ar ay}{l } -n1 & \ n-k & -1 \end{ar ay}\right).
た同様にして, e(|A_{\mathrm{i}}|\cap|A_{2}|) は e(|A_{\mathrm{i}}|\cap|A_{2}|\cap|A_{3}|) ,) e(|A_{\mathrm{i}}|\cap\cdots\cap|A_{k-1}|) を用いて表すことができ, e(|A_{\mathrm{i}}|\cap|A_{2}|\cap|A_{3}|) は e(|A_{\mathrm{i}}|\cap|A_{2}|\cap|A_{3}|\cap|A_{4}|) ,, e(|A_{\mathrm{i} |\cap\cap|A_{k-1}|) を用いて表すことができ,と繰り返していくと,等式 (*) の右辺
は e(|A_{\mathrm{i}}|\cap\cdots\cap|A_{k-1}|) を用いて記述できる.そしてe(|A_{1}|\cap\cdots\cap|A_{k-1}|)=\left(\begin{ar y}{l n-k&+1\ 1& \end{ar y}\right) \left(\begin{ar y}{l n-k&+1\ 2& \end{ar y}\right) +\cdots+(-1)^{n}\left(\begin{ar ay}{l } n-k & +1\ -n2k & +1 \end{ar ay}\right)-であるから,等式 (*) の右辺の値が具体的に計算できる.口§3. \mathrm{H}\mathrm{o}\mathrm{m} 複体§2で近傍複体 \mathrm{N}(G) がgraph coloring problem を解くことに貢献することをみた.このセクションでは, \mathrm{H}\mathrm{o}\mathrm{m} 複体という概念とその例をいくつか述べ, \mathrm{H}\mathrm{o}\mathrm{m} 複体
も彩色数に関する情報を与えることを紹介する.

定義7 G=(V(G), E(H)) , H=(V(H), \mathrm{E}(\mathrm{H})) を有限単純グラフとする. G からH への multihomomorphism とは,写像 $\varphi$ : V(G)\rightarrow 2^{V(H)}\backslash \{\emptyset\} であって,任意の v\in \mathrm{V}(G) に対して f(v) \in $\varphi$(v) を満たすような写像 f : V(G) \rightarrow V(\mathrm{H}) が必ず
グラフ準同型となるようなもののことをいう. G から H へのmultihomomorphism全体の集合を \mathrm{H}\mathrm{o}\mathrm{m} 複体といい, \mathrm{H}\mathrm{o}\mathrm{m}(G, H) と表す、

multihomomorphism はグラフ準同型の一般化になっている.実際,グラフ準同型\{f(v)\} と定義すf : V(G) \rightarrow \mathrm{V}(H) があると, $\varphi$ : V(G) \rightar ow 2^{V(H)}\backslash \{\emptyset\} を $\varphi$(v)るとよい.また, $\chi$(G) > $\chi$(\mathrm{H}) であれば \mathrm{H}\mathrm{o}\mathrm{m}(G, H)=\emptyset となる.
:=

\mathrm{H}\mathrm{o}\mathrm{m} ‘複体”と呼ばれる理由は \mathrm{H}\mathrm{o}\mathrm{m}(G, H) が次のようにして CW‐ 複体と見なすことができるからである.

$\varphi$\in \mathrm{H}\mathrm{o}\mathrm{m}(G, H) とする.まず, 2^{V(H)}\backslash \{\emptyset\} と \triangle_{\# V(H)-1} のface 全体の集合が自然に同一視できることに注意する.この同一視の下で,各 v\in \mathrm{V}(\mathrm{G}) に対して $\varphi$(v)(\subset
V(H)) は \triangle_{\# V(H)-1} のface F_{v}^{ $\varphi$} を定める.そして, $\varphi$ と\displaystyle \prod_{v\in V(G)}F_{v}^{ $\varphi$} (\subset\prod_{v\in V(G)}\triangle_{\# V(H)-1})

112を同一視する. \mathrm{H}\mathrm{o}\mathrm{m}(G, H) の幾何学的実現 |\mathrm{H}\mathrm{o}\mathrm{m}(G, \mathrm{H})| を|\displaystyle\mathrm{H}\mathrm{o}\mathrm{m}(G,H)|:=\bigcup_{$\varphi$\in\mathrm{H}\mathrm{o}\mathrm{m}(G,H)}(\prod_{v\inV(G)}F_{v}^{$\varphi$})と定義する.このようにして \mathrm{H}\mathrm{o}\mathrm{m}(G, H) にCW‐複体の構造が入る.
このCW‐構造に関して次が成り立っている:.

\mathrm{H}\mathrm{o}\mathrm{m}(G, \mathrm{H}) の頂点集合は G から H へのグラフ準同型からなる.

.

$\varphi$\leq $\psi$ in \mathrm{H}\mathrm{o}\mathrm{m}(G, H)\Leftrightarrow\forall u\in V(G) , $\varphi$(u) \subset $\psi$(u) .

\{1 , 2, 3 \} と
例8 \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{3}) について考えてみる, V(K_{2}){ a , ó}, V(K_{3})しよう. $\varphi$ \in \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{3}) を $\varphi$( $\varphi$(a), $\varphi$(b)) と座標のように表すことにする.
\mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{3}) の0‐ce旧よ (1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (3, 2) の6つ.l‐cell は===(1, 23), (12, 3), (2, 13), (23, 1), (3, 12 (13, 2) の6つ.2‐cell以上は出てこない.
よって,各cell の繋がり方を考えると |\mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{3})| は六角形となることが分かる.
また, |\mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{4})| は14個の面 (三角形が8個,四角形が6個)からなる多面体となることが分かる.

例8について,より一般に次が知られている:

事実9 ([3]) |\mathrm{H}\mathrm{o}\mathrm{m}(K_{2;}K_{n})| はantipodal action が入った S^{n-2} と \mathb {Z}_{2} ‐同相になる.
ここで, \mathbb{Z}_{2^{(} \sim|\mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{n})| は K_{2} の線対称軸による折り返し (reflection) (a, b)\mapsto(b, a) から誘導されるものである.
もう一つ,知られている事実を紹介する.

事実10 ([4]) |\mathrm{H}\mathrm{o}\mathrm{m}(C_{5}, K_{n})| はSteifel manifold V_{n-1,2}=\{(x, y)\in \mathbb{R}^{n-1}\times \mathbb{R}^{n-1} | ||x||||y|| =1, x\cdot y=0 \} と \mathb {Z}_{2} ‐同相になる,ここで,C5は頂点数が5のcycle graphであり, \mathb {Z}_{2} \cap |\mathrm{H}\mathrm{o}\mathrm{m}(C_{5}, K_{n})| は C_{5} の1つの線対称軸による折り返し (reflection)から誘導されるもの, \mathb {Z}_{2} へ V_{n-1,2} は (x, y)\mapsto(x, -y) である.
=

\mathrm{H}\mathrm{o}\mathrm{m} 複体についても,近傍複体における定理4のようなgraph coloring problem

を解くことに貢献する評価式が存在するので紹介しておこう.

事実11 ([5]) 任意の有限単純グラフ G と正整数 r\geq 1 に対して, |\mathrm{H}\mathrm{o}\mathrm{m}(C_{2r+1}, G)|
が k ‐連結であれば, $\chi$(G) \geq k+4 が成り立つ.

113§4. \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4}) , \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5}) の3次対称群 S_{3} ‐作用
S3を3次対称群とする.このセクションでは,S3へ |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} S3へ |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5})| がどのように振る舞うかをみる.また,そこから誘導されるホモロジー群
への S_{3} ‐作用の表現行列についても述べる.

V(K_{3})=\{a, b, c\} とする.まず, S_{3} は次のような表示をもつことに注意する:

s_{3}=\langle x, y | x^{3}=1, y^{2}=1, xyxy=1 \}.
ここで, x は K_{3} の時計回り 2/3 $\pi$ 回転 (clockwise rotation) を表し, y は a を通る K_{3}の線対称軸による折り返し(reflaction)を表す.これらは x, y : |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| \rightarrow|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5})|\rightar ow|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5})| を誘導し,この2つの生成元 x, y
により S_{3}\sim|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} S_{3}\cap|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5}) となる.
(1) \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4}) について.
まず, |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| のホモトピー型がどのようになるかを考察しよう. V(K_{4})\{1 , 2, 3, 4 \} とする.先程と同様に $\varphi$\in \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4}) を $\varphi$= ( $\varphi$(a), $\varphi$(b), $\varphi$(c)) と座標のように表すことにする.このとき,=\bullet(i, *, *) ‐typeのcell 全体は \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{3}) , すなわち六角形を構成し,\bullet(ij, *, *) ‐type のcell 全体は \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{2}) \times I , すなわち2線分を構成する.

(i, *, *) ‐typeは i=1 , 2, 3, 4の \left(bgin{ar y}{l 4\ 1 \end{ar y}\ight) 個あるので,六角形が \left(bgin{ar y}{l 4\ 1 \end{ar y}\ight) 個出来る. (ij, *, *) ‐typeは \left(bgin{ar y}{l 4\ 2 \end{ar y}\ight) 個あるので,2線分が \left(bgin{ar y}l 4\ 2 \end{ar y}\ight) 個できる.この \left(bgin{ar y}{l 4\ 2 \end{ar y}\ight) 個の2線分たちは各六角形を ‘橋
渡し ” するような形になっている.これにより空洞が \left(bgin{ar y}{l 4\ 2 \end{ar y}\ight) 個できる.また,3つの六角形によって囲まれる空洞が \left(bgin{ar y}{l 4\ 3 \end{ar y}\ight) -1 個存在することが分かる.よって,|\mathrm{H}\mathrm{o}\mathrm{ }(K_{3},K_{4})|\simeq\left(\begin{ar y}{l 4\ 1 \end{ar y}\right)+\left(\begin{ar y}{l 4\ 2 \end{ar y}\right)+(\left(\begin{ar y}{l 4\ 3 \end{ar y}\right)-1\ve S^{1}=\vee S^{1}13となる.これより1次元ホモロジー群について,

H_{1}(|\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} \mathb {Z})\cong\bigoplus_{13}\mathb {Z}となる. H_{1}(|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} \mathbb{Z}) の 13=

\left(bgin{ar y}{l 4\ 1 \end{ar y}\ight) + \left(bgin{ar y}{l 4\ 2 \end{ar y}\ight) + (\left(\begin{ar ay}{l} 4\ 3 \end{ar ay}\right) - 1) 個の生成元を上のようにとる. S_{3} へ |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| は自然に1次元ホモロジー群への作用 S_{3} \cap\mathrm{H}_{\mathrm{i} ( |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} \mathbb{Z}) を誘導する.この生成元に関する S_{3}HÎ (|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} \mathbb{Z})の表現行列を計算すると次のようになった:114

X_{4}, Y_{4} をそれぞれ鍛, y_{*} : \oplus_{13}\mathbb{Z}\rightar ow\oplus_{13}\mathbb{Z} に対する表現行列とすると,

X_{4}=[-12 10 0 1 0 -1 0 \displaytefrc{0} 1- 0 1
Y_{4}=[0 10 0 10 -10 -10 -10 -10 -10 -10 -10 \displaytefrc{0}1- 10 ]となる.この X_{4}, Y_{4} は群の関係式 X_{4}^{3}=

E, Y_{4}^{2} =E, X_{4}Y_{4}X_{4}Y_{4}=

E を確かに満たしていることが確認できる.また, x, y : |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| \rightarrow |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| はともにfree action なので Lefschetz の不動点定理より, \mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}X_{4}=1, \mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}Y_{4}=1 とならなければならないが,これも確かに満たされている.
(2) \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5}) について.
まず, |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| のときと全く同様にして, |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5})| のホモトピー型を決定することができる. V(K_{5})=\{1 , 2, 3, 4, 5 \} とする.このとき,\bullet(i, *, *) ‐type のcell 全体は \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{4}) , すなわち14面体を構成し,115\bullet\bullet(ij, *, *) ‐type のcell 全体は \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{3}) \times I , すなわち六角柱を構成し,(ijk, *, *) ‐type のcell 全体は \mathrm{H}\mathrm{o}\mathrm{m}(K_{2}, K_{2}) \times\triangle_{2_{\dot{\mathrm{K} } すなわち2つの三角形を構成する.

|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})| のホモトピー型は S^{1} のwedge sum となったが, |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5})| のホ
モトピー型は次元が1つ上がり S^{2} のwedge sum となる.その個数は |\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4})|のときと全く同様に数え上げることができ,|\mathrm{H}\mathrm{o}\mathrm{ }(K_{3},K_{5})|\simeq\ve S^{2}\left(\begin{ar y}{l 5\ mathrm{l} \end{ar y}\right)+\left(\begin{ar y}{l 5\ 2 \end{ar y}\right)+\left(\begin{ar y}{l 5\ 3 \end{ar y}\right)+(\left(\begin{ar y}{l 5\ 4 \end{ar y}\right)-1=\vee S^{2}29となる.これより2次元ホモロジー群について,

H_{2}(|\displaystyle \mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5} \mathb {Z})\cong\bigoplus_{29}\mathb {Z}となる. H_{2}(|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5} \mathbb{Z}) の 29=

\left(bgin{ar y}{l 5\ 1 \end{ar y}\ight) + \left(bgin{ar y}{l 5\ 2 \end{ar y}\ight) + \left(bgin{ar y}{l 5\ 3 \end{ar y}\ight) +(\left(\begin{ar ay}{l} 5\ 4 \end{ar ay}\right) - 1) 個の生成元をH_{1}(|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{4} \mathbb{Z}) の生成元をとったときと同様にとる.この生成元に関する
S_{3}\cap H_{2}(|\mathrm{H}\mathrm{o}\mathrm{m}(K_{3}, K_{5} \mathbb{Z}) の表現行列を計算すると次のようになった:
X_{5} , 鶏をそれぞれ侮, y_{*} : \oplus_{29}\mathbb{Z}\rightar ow\oplus_{29}\mathbb{Z} に対する表現行列とすると,
10列分

X_{5}=

116

Y_{5}=\rightarrow
5列分となる.この X_{5}, Y_{5} は X_{4}, Y_{4} のときと同様に,群の関係式の条件 X_{5}^{3}=E, Y_{5}^{2}=
E, X_{5}Y_{5}X_{5}Y_{5}=E と,Lefschetz の不動点定理の条件 \mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}X_{5}=-1, \mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{e}Y_{5}=-1を確かに満たしていることが確認できる.

参考文献[1] László Lovász, Kneser’s conjecture, chromatic number and homotopy,
J.Combinatorial Theory, Ser.A 25(1978), 319‐324.

[2] Mark de Longueville, A Course in Topological Combinatrics, Springer Sci‐
ence + Business Media New York, 2013.

[3] Babson, Kozlov, COMPLEXES OF GRAPH HOMOMORPHISMS,
arXiv:math/0310056\mathrm{v}4 [math.CO] 26 Mar 2005.

[4] James Dover, Murad Ózaydin, Steifel manifold and coloring the pentagon,
Journal of Combinatorial Theory, Series A 121 (2014) 74‐88

117[5] Babson, Kozlov, PROOF OF THE LOVÁSZ CONJECTURE,
arXiv:math /0402395\mathrm{v}3[ math. \mathrm{C}\mathrm{O}] 1\mathrm{S} Jul 2005.