89

数理解析研究所講究録第2060巻 2018年 89-95

近傍複体の基本群について
松下尚弘

京都大学理学研究科数学教室

1

はじめに

本講演では論文 [3] の概要を述べる.まず基本的な用語を定義から始める.
グラフとは集合 \mathrm{V}(G) とV (G) 上の対称律を満たす二項関係 \mathrm{E}(G) の組 G=(V(G)\dot{}, E(G))のことである.すなわち \mathrm{E}(G) は V(G)\times \mathrm{V}(G) の部分集合で,「 (v, w)\in E(G)\Rightarrow(w, v)\inE(G) 」 を満たすものである.したがって我々のグラフは,ループはあってもよいが二重線を持たない非有向グラフである.一般に非有向グラフで,ループも二重線も持たないグラフのことを単純グラフという.近傍複体の周辺分野の慣例により,ループがあってもよいものとする.

グラフ G と H に対し,写像 f : V(G) \rightar ow \mathrm{V}(\mathrm{H}) で (f\times f)(E(G)) \subset \mathrm{E}(H) を満たすもの

をグラフ準同型という.幾何学的なイメージでは,グラフ準同型はグラフの問の連続写像というだけでなく, G の辺を H の辺に等長に写しているものとみなすことができる.グラフを対象とし,グラフ準同型を射とする圏をグラフの圏といい \mathcal{G} で表す.

次にグラフの彩色問題について述べる.グラフ G に対し,

G の n ‐彩色とは,頂点集合

V(\mathrm{G}) から n 点集合 [n]=\{1, \cdots , n\} への写像 c : V(G)\rightarrow[n] であって,「 (v, \mathrm{c}v)\in E(G)\Rightarrowc(v)\neq \mathrm{c}(w) 」 を満たすものである.グラフ G の彩色数とは, G の n‐彩色が存在する様な最小の n のことをいい, $\chi$(G) で表す.グラフの彩色数を決定する問題をグラフの彩色問題といい,これはグラフ理論において昔から研究されてきた重要な問題である.
後々のために,nn‐彩色は特別なグラフ準同型とみなすことができることを述べておく.

頂点完全グラフ K_{n} を V(K_{n})=[n], E(K_{n})=\{(i, j)\in [n]\times [n] |i\neq j\} とおく.このとき G の n‐彩色は G から K_{n} へのグラフ準同型と同一視することができる.したがってグ

ラフの彩色問題は,グラフ準同型の存在問題,すなわち,与えられた二つのグラフ G とH に対し,G から H へのグラフ準同型が存在するかどうかという問題と,自然に一般化できる.

Lovasz は[2] において以下のように定義される近傍複体を定義し,その位相的な性質がグラフの彩色数に下限を与えることを証明した.まずグラフ G とその頂点 v に対し,N(v) または N_{G}(v) によって,vに隣接する G の頂点全体のなす集合とする.すなわち

90

N(v)=\{w\in V(G) | (v, w) \in \mathrm{E}(G)\} である. G の近傍複体 \mathrm{N}(G) とは,頂点集合を G の孤立していない頂点全体 (すなわち v\in V(\mathrm{G}) で N(v)\neq\emptyset なるもの) とし,N(G)= { $\sigma$\subset V(G) |\# $\sigma$<\infty で $\sigma$\subset N(v) となる v\in V(G) が存在する.}により定義する.Lovasz [2] は以下の定理を示した :定理1.1 (Lovasz [2]). グラフ G に対し, \mathrm{N}(G) が n ‐連結ならば $\chi$(G) \geq n+3 である.
Lovasz は定理1.1を以下の Kneser グラフの彩色数の決定に応用した.

まず n と k を正の整数とし, n\geq 2k とする.Kneser グラフ KG_{n,k} を V(KG_{n_{\rangle}k})=\{ $\sigma$\subset[n] |\# $\sigma$=k\}, E(KG_{n,k})=\{( $\sigma$, $\tau$) | $\sigma$\cap $\tau$=\emptyset\} とする.

命題1.2 (Lovasz [2]). N(KG_{n,k}) は (n-2k-1) ‐連結である.
定理1.1と命題1.2により次が得られる :定理1.3 (Kneser 予想 [2]). $\chi$(KG_{n,k})=n-2k+2
本講演では近傍複体の基本群が組合せ論的な定式化を持つ群と同型であることを証明する.正の整数 r と点付きグラフ (G, v) に対し, r ‐基本群と呼ばれる群 $\pi$ í(G, v) を定義する. $\pi$ í(G, v) には偶数部分と呼ばれる自然な部分群 $\pi$_{1}^{r}(G, v)_{ev} が定まり, \mathrm{N}(G) の基本群
は $\pi$_{1}^{2}(G, v)_{ev} と対応することがわかる.第2節で r ‐基本群を定義し,第3節で Kneser グ
ラフの r ‐基本群の計算を述べる.

最後の第4節で r ‐被覆写像について述べる.ある程度良い性質を持った位相空間の場合,位相空間の基本群と被覆写像との間には密接な関係があるが,それと同様に,対応する被覆写像の概念が r ‐被覆写像である.

rr‐基本群に‐基本群の部分群と連結な点付き r ‐被覆とは自然に対応する.特に偶数部分 í (G, v)_{ev} に対応する r ‐被覆は,Kronecker二重被覆 [1]と呼ばれる特別な r ‐被覆である. $\pi$_{1}(N(G), v) が $\pi$_{1}^{2}(G, v)_{ev} と対応したことを合わせると,$\pi$

近傍複体の上の被覆写像とは K_{2} \times G 上の r ‐被覆という離散的に記述することができる.

2r‐基本群

以下 r を正の整数とする.点付きグラフとはグラフ G と G の頂点 v の組 (G, v) のことである.グラフ疏を V(P_{n})=\{0, 1, , n\} かつ \mathrm{E}(P_{n})=\{(v, w) | |v-w|=1\} により定義する.ここで \mathrm{V}(P_{n}) は 0 を含んでいることに注意する.

点付きグラフ (G, v) に対し,グラフ準同型 $\gamma$ : P_{n} \rightarrow G で $\gamma$(0) = $\gamma$(n) =v となるもの

を,長さ n の (G, v) のノレープという. (G, v) の)レープ $\varphi$ に対し, l( $\varphi$) で $\varphi$ の長さ,すなわ
ち $\varphi$ : P_{n}\rightarrow G の n を対応させるものとする. (G, v) のループ $\varphi$ と $\psi$ に対し,以下の二つの条件を考える.ここで r は節の冒頭で定めたある正の整数である :(1) l( $\psi$) =l( $\varphi$)+2 であり, x \in \{0, 1, , l( $\psi$)\} が存在して, $\varphi$(i) = $\psi$(i) , (i\leq x) かつ$\varphi$(i)= $\psi$(i+2) , (i\geq x) が成り立つ.

91(2) l( $\varphi$)=l( $\psi$) で,\#\{i\in\{0, 1, , l( $\varphi$) | $\varphi$(i)\neq $\psi$(i)\}\}<rが成り立つ.

ここで(1) の条件は,と $\psi$ は x までは同じ道であるが, x+1 において $\psi$ は $\varphi$ とは別の頂点に向かうものの, $\psi$(x+2) は $\psi$(x) = $\varphi$(x) に戻り,その後は $\varphi$ と $\psi$ は同じように進$\varphi$

むということである.

(G, v) のループ全体の集合を $\Omega$(G, v) と表し, $\Omega$(G, v) において上記の (1) と (2) で生成される同値関係を \simeq_{r} で表す.これらの用語により,

r‐基本群は以下のように定式化される :定義2.1 (松下). (G, v) の r ‐基本群 $\pi$ í (G, v) とは,商集合 $\Omega$(G, v)/\simeq_{r} のことである.
ループの結合により $\pi$ í(G, v) は群になる.
次に $\pi$ í(G, v) の偶数部分について述べる.

$\varphi$, $\psi$ \in$\Omega$(G, v) に対し,同値関係 \simeq_{r} の定義

から, $\varphi$\simeq_{r} $\psi$ ならば, l( $\varphi$) と l( $\psi$) の偶奇は変わらない.したがって
l : $\pi$ í (G, v)\rightarrow \mathbb{Z}/2,[ $\varphi$]_{r}\mapsto l( $\varphi$)+2\mathbb{Z}はwell‐defined な群準同型写像である.ここで [ $\varphi$]_{r} により $\varphi$ が属す \simeq_{r} の同値類 (r ‐ホモトピー類ということにする) を表す.この準同型の核を $\pi$ í (G, v)_{ev} で表して, (G, v) のr‐基本群 $\pi$ í (G, v) の偶数部分ということにする.
定義から明らかなように,偶数部分は $\pi$ í(G, v) の指数が1または2の部分群である.連結グラフ G に対し, $\chi$(G)\leq 2 なることと,長さが奇数のループが存在しないことは同値であることは良く知られている (Zornの補題から簡単に示せる) . ここで $\chi$(G) \leq 2 ということは G がいわゆる二部グラフであることを意味する.以上のことから点付きグラフ(G, v) に対し, $\pi$_{1}^{r}(G, v) = $\pi$ í (G, v)_{ev} となる場合は,vを含む G の連結成分が,二部グラフであることと同値であることが容易に示される.

主定理をより完全な形に述べるために,r‐近傍複体なるものを定義しておく.これはLov島 \mathrm{z} の近傍複体の一般化であって,1‐近傍複体 N_{1}(G) は近傍複体に一致する.
G をグラフ,vを G の頂点とする.このとき r ‐近傍瓦(v) をN_{1}(v)=N(v) , N_{i+1}(v)=\displaystyle \bigcup_{w\in N_{i}(v)}N(w)と帰納的に定義することにより定める.

r‐近傍複体 N_{r}(G) をN_{r}(G)= { $\sigma$\subset V(G) |\# $\sigma$<\infty であり, $\sigma$\subset N_{r}(v) となる v\in V(G) が存在する.}と定義する.論文 [3] の主結果は以下のものである :定理2.2 (松下).点付きグラフ (G, v) で N(v)\neq\emptyset なるとき,自然な群同型$\pi$_{1}^{2r}(G, v)_{ev} \rightar ow^{\simeq\underline{} $\pi$ Î (N_{r}(G), v)が存在する.

92

特に r=1 のときを考えれば, $\pi$_{1}^{2}(G, v)_{ev}\cong$\pi$_{1}(N(G), v) である.
節の最後にサイクルグラフ C_{n} の r ‐基本群について述べる.まずサイクルグラフの定義を述べる.

nを3以上の整数とするとき, V(C_{n})=\mathbb{Z}/n\mathbb{Z}, E(C_{n})=\{(x, x\pm 1) |x\in \mathbb{Z}/n\mathbb{Z}\}で定義されるグラフがサイクルグラフである.すなわち n ‐角形の頂点を頂点とし,辺を辺とするようなグラフ C_{n} である.以下に見るように, n が偶数か奇数かにしたがって,r‐基本群の記述はだいぶ変わってくる.

命題2.3. 次が成り立つ(1) 2以上の整数 n に対し,
\mathrm{m}_{1}^{r}(C_{2n})\congであり,その生成元は偶である.

\left{\begin{ar y}{l \mathb{Z}&(r<n)\ 1&(r\geqn). \end{ar y}\right.

(2) 1以上の整数 n に対し$\pi$_{1}^{r}(C_{2n+1})\congであり,その生成元は奇である.

3\left{\begin{ar y}{l \mathb{Z}&(r\leq2n)\ mathb{Z}/2\mathb{Z}&(r\geq2n) \end{ar y}\right.

Kneser グラフの r ‐基本群
ここでは Kneser グラフ KG_{n,k}, (k\geq 1, n\geq 2k) の r ‐基本群を決定する.

まず r ‐基本群と基点との関係について述べる.

v, w\in \mathrm{V}(G) が G の同じ連結成分に含まれているならば,位相空間の基本群の場合と同様にして, $\pi$ í (G, v) と $\pi$ í (G, w) が同型であることがわかる.そこで特に基点の取り方によらないときは $\pi$ í(G) と書いて基点を省略することにする.

まず n=2k のときを考えると, KG_{n,k} は K_{2} の直和である.したがって $\pi$_{1}^{r}(KG_{n,k}) は全ての基点に関して自明である :命題3.1. 任意の r\geq 1 に対し,$\pi$

í (KG_{2k,k})=1 である.

つついて n>2k+1 のときを考える.このときLovasz の結果 (命題1.2) により N(KG_{n,k})は単連結なので,特に KG_{n,k} は連結であり, $\chi$(KG_{n,k})\geq 3 である.したがって $\pi$_{1}^{2}(G, v)_{ev}=$\pi$_{1}(N(G))= 1 であり, $\pi$_{1}^{2}(G, v)_{ev} は $\pi$_{1}^{2}(G, v) の指数2の部分群である.

$\pi$

í (G, v) , (r\geq 2)

は $\pi$_{1}^{2}(G, v) の商群であることを考えると,次が分かる.
命題3.2. n>2k+1 ならば r\geq 2 に対し $\pi$_{1}^{r}(KG_{n,k})=\mathbb{Z}/2 かつ $\pi$_{1}^{r}(KG_{n,k})_{ev}=1 である.

93

したがって本質的に難しい場合は KG_{2k+1,k} の r ‐基本群ということになる.
2‐基本群に関して述べる. KG_{2k+1,k} の特徴から, $\varphi$, $\psi$ を KG_{2k+1,k} のループで , $\varphi$ と $\psi$ が条件 (2)2を満たすならば, $\varphi$= $\psi$ となることがわかる.これは KG_{2k\frac{1}{-}1,k} が4‐ サイクルグ
ラフ (正方形のグラフ) の埋め込みを持たないことから容易にわかる.この事実は $\varphi$\simeq 2 $\psi$
ならば $\varphi$\simeq 1 $\psi$ であることを意味する.すなわち自然な全射 $\pi$_{1}^{1}(KG_{2k+1,k})\rightarrow $\pi$ 1(KG_{2k+1,k})は全射であり, $\pi$_{1}^{1}(KG_{2k+1,k}) は KG_{2k+1,k} を通常のやり方で1次元単体複体とみなしたときの基本群に一致する.したがって $\pi$_{1}^{2}(KG_{2k+1,k}) を計算するには, KG_{2k+1,k} のEuler数を計算すればよいので,詳細は省く.
一方で r\geq 3 のときは以下のことがわかる :定理3.3 (松下 [3]). 任意の k\geq 1 に対し $\pi$_{1}^{3}(KG_{2k+1,k}) =\mathbb{Z}/2, $\pi$_{1}^{3}(KG_{2k+1,k})=1 が成り立つ.

証明は長いので省略する.ともかく以上により Kneserグラフの r ‐基本群を全て決定することができた.

定理3.3は以下のようにグラフ準同型の非存在性に応用することができる.

系3.4 (松下 [3]). KG_{2k+1,k} からC5へのグラフ準同型は存在しない.
証明を述べる前に,この系について,既存のグラフ準同型の障害との比較を行う.

まず定理1.3から KG_{2k+1,k} から K_{3}\cong C_{3} へのグラフ準同型は存在する.一方, KG_{2k+1,k}から C_{7} にグラフ準同型が存在するならば, C_{7} から C_{5} にグラフ準同型が存在するため,KG_{2k+1.k} から C_{5} にグラフ準同型が存在することになり,系3.4に反する.したがって系
3. 4\ovalbox{\t\smal REJECT} よ KG_{2k+1,k} から C_{2n+1} へのグラフ準同型が存在する様な最大の n は1であることを示している.

グラフ準同型に関するよく知られた障害として,奇内周 (odd girth)がある.グラフ Gの奇内周とは, C_{2n+1} から G へのグラフ準同型が存在する様な最小の 2n+1 のことをいい, g_{0}(G) で表す.二つのグラフ G と H に対し, G から H へのグラフ準同型が存在するならば,奇内周の定義から g_{0}(G) \geq g_{O}(H) がわかる.一方で g_{0}(KG_{2k+1,k})2k+1 で=g_{O}(C_{5})=5 であるため,( k\geq 2 に対しては) 奇内周から KG_{2k+1,k} から C_{5} にグラフ準同型が存在しないことは示すことができないことがわかる.

もう一つグラフ準同型の障害として知られている者として,分数的彩色数(fractionalchromatic number) がある.これは有限グラフ G に対し$\chi$_{f}(G)=\displaystyle \inf

{ \displaystle\frac{n}m | から KG_{n,m} へのグラフ準同型が存在する.}Gにより定まる G の不変量である.有限グラフ G に対し, $\chi$_{f}(G) が有理数であることが知られており,グラフ G からグラフ H へのグラフ準同型が存在するならば $\chi$_{f}(G)\leq$\chi$_{f}(\mathrm{H}) となることが知られている.Kneser グラフ KG_{n,k} に対しては $\chi$_{f}(KG_{n,k})=n/k, $\chi$(C_{2n+1})=(2n+1)/2 となることが知られている.したがって $\chi$_{f}(KG_{2k+1,k})=(2k+1)/k, $\chi$_{f}(C_{5})=945/2となる.したがって k\geq 2 ならば KG_{2k+1,k} から C_{5} にグラフ準同型が存在しないことを,分数的彩色数から導くことはできない.分数的彩色数に関しては[4] などに書かれている.

系3.4の証明を与える.もしグラフ準同型 f:KG_{2k+1,k} \rightarrow C_{5} が存在したとし,その3‐基本群に誘導する写像 f_{*} : $\pi$_{1}^{3}(KG_{2k+1,k})\rightarrow$\pi$_{1}^{3}(C_{\overline{i\supset} ) を考えると,定理3.3より $\pi$_{1}^{3}(KG_{2k+1,k})\cong\mathbb{Z}/2 で,一方 $\pi$_{1}^{3}(c_{\ulcorner}l\mathrm{J}) \cong \mathb {Z} だから f_{*} は自明な群準同型である.一方, $\pi$_{1}^{3}(KG_{2k+1,k}) の生
成元 $\alpha$ は偶数部分に含まれない (すなわち奇数の長さを持つループで代表される) ため,f_{*}( $\alpha$) も偶数部分に含まれず,したがって f_{*}( $\alpha$)\neq 0 となり,これは矛盾である.

4r‐被覆写像について

グラフ準同型 p : G\rightarrow H であって,任意の v\in V(G) に対し p|_{N_{i}(v)} : N_{i}(v) \rightarrow N_{i}(\mathrm{p}(v))
が 1\leq i\leq r に対し全単射であるとき, p は r ‐被覆写像であるという.簡単にわかるように,
この条件は任意の v\in V(G) に対し p|_{N(v)} : N(v) \rightarrow N(\mathrm{p}(v)) が全射で, p|_{N_{r}(v)} : N_{r}(v)\rightarrow
N_{r}(p(v)) が単射であることと同値である.
r‐基本群と r ‐被覆写像は,ちょうど位相空間における基本群と被覆写像における関係が成り立つ.そのことを述べるためにいくつかの用語を準備しておく.

(H, w) が (G, v) の r ‐被覆であるとは,何らかの r ‐被覆写像 p_{H} : H\rightarrow G で基点を保つものが与えられているもののこととする.特に H が連結のとき (H, w) は連結な r ‐被覆であるという. (H_{0}, w_{0}) と (H_{1}, w_{1}) を (G, v) 上の r ‐被覆とするとき,グラフ準同型 f : (H_{0}, w_{0})\rightarrow(H_{1}, w_{1}) であって p_{H_{1}}\circ f=p_{H}。を満たすものを (点付き) r ‐被覆の間の射という. r ‐被覆写像の定義から容易にわかることとして,r‐被覆の射はそれ自体 r ‐被覆になる.

定理4.1. (G, v) を点付きグラフとする.このとき以下が成り立つ :(1) 基点を保つ r ‐被覆写像 p ; (H, w) \rightarrow (G, v) は単射 p_{*} : $\pi$ í (H, w) \rightarrow $\pi$ í (G, v) を誘導する.

(2) 任意の $\pi$_{1}^{r}(G, v) の部分群 $\Gamma$ に対し,連結な点付きグラフからの r ‐被覆写像 p : (H, w)\rightarrow(G, v) であって, p_{*} : $\pi$_{1}^{r}(H, w) \rightarrow $\pi$ í (G, v) の像が $\Gamma$ に一致するものが存在する ((1)
から $\pi$_{1}^{r}(H, w)\cong $\Gamma$ である) .

(3) $\Gamma$_{0} と $\Gamma$_{1} を $\pi$ í (G, v) の部分群とし, p、: (H_{i}, w_{l}) \rightarrow (G, v) を (G, v) 上の連結な r ‐被覆で p_{i*}($\pi$_{1}^{r}(H_{i}, w_{i})) が几になるものとする.このとき (H_{0}, w_{0}) から (H_{\mathrm{i} , w\mathrm{i}) への r ‐被覆の射が存在することと, $\Gamma$_{0}\leq$\Gamma$_{1} なることは同値であり,存在する場合,その射は一意に定まる.特に p ( $\pi$ í(H, w) ) = $\Gamma$ となる r ‐被覆 p : (H, w) \rightarrow (G, v) は同型を除*いて一意である.

特に偶数部分 í (G, v)_{ev} に対応する r ‐被覆は Kronecker 二重被覆と呼ばれる特別なグラ$\pi$フである.その定義を述べるために,グラフのテンソル積について述べる.グラフ G と

95

H に対し,その積 G\times H をV(G\times H)=V(G) \times V(H),E(G\times H)=\{((v, w), (v', w | (v, v')\in E(G) , (w, w')\in \mathrm{E}(\mathrm{H})\}として定義する.このとき射影 p_{1} : G\times H\rightarrow G とp2 : G\times H\rightarrow H はグラフ準同型である.
G 上の Kronecker —−重被覆とは,テンソル積 K_{2}\times G のことである.第二射影 K_{2}\times G\rightarrow Gは任意の正の整数 r に対し r ‐被覆写像となる.

Kronecker 二重被覆に関してわかっていることを手短に述べる. G が連結のとき, $\chi$(G) >2 なることと K_{2}\times G が連結であることは同値である. $\chi$(G)=2 ならば K_{2}\times G は G の二つの直和である.

第一射影 K_{2}\times G\rightarrow G\rightarrow K_{2} はグラフ準同型であるから, K_{2}\times G は二彩色可能である.
連結グラフ G で $\chi$(G) > 2 なるものに対し, G 上の二重被覆 H で $\chi$(H) =2 なることと,H=K_{2} \times G となることは同値である.

例4.2. 自然な射影によりグラフ準同型 C_{km} \rightarrow C_{m} が定義される.これがいつ r ‐被覆写像になるのかを述べる. k> 1 とする.

まず m=2n とする.このとき C_{km}\rightarrow C_{m} は (n-1) ‐被覆写像であるが,はない.

一方,m=2n+1 のとき,k>2 のとき,C_{2m} \rightarrow C_{m} は任意の正の整数

rn‐被覆写像でに対し ‐被覆写像である.
rC_{km}\rightarrow C_{m} は (m-1) ‐被覆写像であるが m ‐被覆写像ではない.この記述と,サイクルの r 基本群の記述とを比べてみると,実際に定理4.1が成り立っていることが確かめられる.

例4 3.
\cdot

n, k を正の整数で n > k とする.もし n > 2k + 1 ならば,あるから,$\pi$_{1}^{2}(KG_{n,k})_{ev} は自明でKG_{n,k} のみである.
KG_{2k+1,k} 上には3‐被覆は KG_{2k+1,k} およびK2 \times KG_{2k+1,k} のみである.2‐被覆はこの場
r\geq 2 に対し KG_{n_{:}k} 上の r- 被覆は KG_{n,k} 自身と K2 \times

合1‐ 被覆と同じであり,無限個存在する.
References[1] W. Imrich, T. Pisanski, Multiple Kronecker covering graphs, European J. Combin.
29 (2008), 1116‐1122.
[2] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Ser. \mathrm{A}
25 (3) (1978), 319‐324.
[3] T. Matsushita, Fundamental groups of neighborhood complexes, J. Math. Sci. Univ.
Tokyo 24 (2017), 321‐353.
[4] E. R. Scheinerman, D. H. Ullman, Fractional graph theory, New York: Wiley‐Interscience (1997)