数理解析研究所講究録 1241 巻 2001 年 84-93

84
極大鎖グラフを用いた順序複体のシェリング可能性の判定について-Maximal chain graph does not contain essential cycles ensures theshellability of a order complex?
-

東京理科大学工学部伊藤美保 (M. Ito), 平林隆一 (R. Hirabayashi)1
東京理科大学工学部 (Science University of Tokyo)

1

はじめに

有限半順序集合は, それに含まれる全順序部分集合を単体とみなすことによって, (組合せ的) 単体的複体 (順序複体) と考えることができる. 単体的複体のシェリング可能性 (shellability)
年盛んに研究されているが, こ
こでは順序複体のシエリング可能性に限って議論する ([1], [2], [3], [4], [5], [10]). Bj\"omer (1980, [1]) によって,順序複体のシェリング可能性に対する十分条件が与えられ, 池辺, 平林 (1997, [5]) によって極大鎖グラフが本質的サイクルを持たないことが必要であることが示された. しカル, [5] ではそのための有効なアルゴリズムが示されていない. また, 与えられた条件が十分条件となっているかどうかについても述べられていない. 本論文では, 極大鎖グラフが本質的サイクルを持たないという条件を効率的に調べるのに役立つ定理とこの条件が十分条
件とはならないことを, Dunce hat ([15], [17]) の分割から誘導される順序複体を用いて証明する.
$\overline{\not\in}\backslash$

2

用語の定義
$V=\{v_{1},$ $\ldots$, v 訂を有限集合とする.

$V$

上の (抽象的, 組合せ的) 単体的複体$\Delta$とは, $V$ の部分集合の族で,(1) $G\in\Delta$ かつ $F\subset G$ ならば, $F\in\Delta$ ,, $i=1,$(2)$\{v_{1}.\}\in\Delta$$\ldots,$$n$の次元の面といい, 市 mF $=|F|-1$ を $F$ の次元という.
とは $\dim\Delta=\max\{\dim F|F\in\Delta\}$ で定義する.
によって生成されるの面 {の部分複体を (おく. 単体的複体の極大面をファセット (facet) という. また, 単体 $F\in\Delta$ の面 $G\subset F$ で $|G|=|F|-1$ をであるときをいう ([16]). また,$\Delta$の要素 $F$ を$\Delta$$\Delta$$\Delta$$\Delta$$F.\cdot 1:\in t$$F_{1}.\rangle:\in t$$\Delta$満たすものを $F$ のファセットという. 単体的複体(pure) 純な単体的複体という.

$\Delta$の任意のファセットの次元がすべて等しいとき,$\Delta$を純

定義 21(Bruns and Herzog[16]): 純な単体的複体がシェリング可能であるとは, 以下の同値な 3 つの条を与えるこのファセットの集合に線形順序
件のいずれかが満足されるときをいう : 単体的複体$\Delta$$\Delta$$F_{1},$$\ldots,$$F_{m}$とができ,のファセットによって生成される.
は全ての $i(2\leq i\leq m)$ に対して,(1)は唯一の極小元を持つ.
(2) 任意の $i(2\leq i\leq m)$ に対して, 集合と $k\in\{1,2, \ldots, i-1\}$ が存在する.
となる(3) 任意の $j(1\leq j<i\leq m)$ に対して,$\langle F_{\dot{*}}\rangle\cap(F_{1},$$\ldots,$$F_{1-1}.\rangle$$F_{\dot{l}}$$\{F:F\in(F_{1}, \ldots, F_{1}.\rangle, F\not\in(F_{1}, \ldots, F_{1-1}.\rangle\}$$i,$$F_{\dot{l}}\backslash F_{k}=\{v\}$上の定義における同値な条件 (1), (2) およひ (3) を満足する(shelling) という.

$v\in F_{1}.\backslash F_{j}$$\Delta$のファセットの線形順序を$\Delta$のシエリングシェリング可能性を再帰的に定義すると次のようになる $([7],[8],[9])$ . すなわち , 次元が の純な単体的複体
を次の再帰的な条件をみたすように与えることができるとき,のファセットの集合の線形順序$d$$F_{1},$ $F_{2},$$\ldots,$$F_{t}$

はシェリング可能であるという.

(1)$\underline{t=1\text{のとき}\Delta|1^{\backslash }\grave{J}\text{ェ}\prime\mathrm{r}\sqrt[\backslash ]{}\text{グ}\beta\urcorner \mathrm{a}\mathrm{e}\text{て}.\text{ある}}$l 脂 a@ms.kagu.

$\mathrm{s}\mathrm{u}\mathrm{t}.$

ac.jp

.

$\Delta$$\Delta$

85) はシエリング可能であり, (U...
のときは, ( $F,$(2) 2のファセットの次元がすべて $d-1$ である.
$\mathrm{U}F_{t-1}$$\mathrm{U}\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT} t\ovalbox{\tt\small REJECT} j$$F_{1}\mathrm{U}\ovalbox{\tt\small REJECT}$U...

$\mathrm{U}F_{t-1}$)$\cap(F\mathrm{D}, (2\ovalbox{\tt\small REJECT} j\ovalbox{\tt\small REJECT} t)$

ウ. こ
を $P$ の鎖とをみたすとき,がを半順序集合とする.
$\Delta(P)$をのとき, $r-1$ をこの鎖の長さという. $P$ の長さとは, $P$ の鎖の長さの最大値をいうものとする. また,$P$ に付随する順序複体とウ. $P$ を半$P$ のすべての鎖からなる集合とすると, $\Delta(P)$ は単体的複体となるので,$\mathrm{A}\backslash$$P$$v_{i_{1}},$$\ldots,$$\{v_{i_{1}}, \ldots, v_{i_{r}}\}$$v_{i_{1}}\leq\cdots\leq v_{i_{r}}$$v_{i_{r}}\in P$$\mathrm{A}\backslash$, rank でより小さい元からなる $P$ の鎖の長さの最大値を順序集合とする. $v\in P$ のランクとは, と表すものとする. $P$ を半順序集合とする. $x\leq y,$ $x\neq y$ 力\searrow x $\leq z\leq y$ なら $x=z$ が $y=z$ となるとき,である鎖であるとき, 鎖がをカバーするといい $x\prec y$ と書く.
はを細分不能な鎖という. また, 集合の包含関係において極大な鎖を極大鎖と ウ.
$\mathrm{A}\backslash \mathrm{A}\backslash$

$v$

$v$

$v$

$y$

$\{v_{i_{1}}, \ldots, v_{i_{r}}\}\subset P$$x$$v_{i_{1}}\prec v_{i_{2}}\prec\cdots\prec v_{i_{r}}$$\mathrm{A}\mathrm{a}$$\{v_{\dot{\iota}} , \ldots, v_{\dot{\alpha}_{r}}\}1$

半順序集合が最小元と最大元を持つとき有界な半順序集合という. 半順序集合のすべての極大鎖が同じ長さをのう. 明らかに,持つとき, 純な半順序集合という. 有界かつ純な半順序集合を次数付き半順序集合とシェリング可能性を考えるためには, 次数付き半順序集合についてのみ考えればよ ことがわかる.
$\Delta(P)$$\mathrm{A}\backslash$$\mathrm{A}\backslash$

半順序集合 $(P, \leq)$ が局所上半モジュラー半順序集合であるとは, $x\prec u,$
存在して, $u\prec y,$ $v\prec y$ かつ $y\leq t$ を満たすときをいう.

$v$

かつ $u,$ $v<t$ であるとき, $y\in P$ 力\tilde

定理 22(Bj\"orner[1]): 局所上半モジュラーな次数付き半順序集合に付随する順序複体はシエ ’) ング可能である.
が局所弱上半モジュラーであるとは, $x\prec u,$$(P, \leq)$

在して, $x\prec w_{i}(1\leq i\leq\ell),$ $u=w_{0},$$v$

かつ $u,$ $v<t$ であるとき,$w_{1},$$\ldots,$$w\ell,$ $y_{1},$$\ldots,$$y_{\ell+1}\in P$

力\tilde 存$w_{\ell+1}=v\prec y_{\ell+1}$ 力 つ $y_{i}\leq t(1\leq i\leq\ell+1)$$\backslash$$w_{1}\prec y_{1},$$w_{1},$ $w_{2}\prec y_{2},$$\ldots,$$w_{\ell},$を満たすときをいう.
定理 23(池辺, 平林 [5]):$(P, \leq)$

を次数付き半順序集合で, $\Delta(P)$ がシエリング可能であるとすると, $P$ ま局

所弱上半モジュラーである.

を次数付き局所弱上半モジュラー半順序集合とし,$(P, \leq)$$\mathcal{M}$

を $P$ のすべての極大鎖からなる集合とする. このとき, $E(P)=\{\{m, m’\} : m, m’\in \mathcal{M}, |m\backslash m’|=1\}$ として, グラフ $G(P)=(\lambda 4, E(P))$ をつくる.
$(\{v\}=\{m\backslash m’\})$ を彩色することにする. この辺彩色されたグラフ
フの各辺 $\{m, m’\}\in E(P)$ に色
このグラ$i=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}v$$G(P)$ を $P$ の極大鎖グラフということにする.

また, $(P, \leq)$ を次数付き局所弱上半モジュラー半順序集合とし,$S\subset \mathcal{M}$とする. $G(P)$ が $S$ に関して性質 (C)を持つとは:(C)$G(S)$

を $S$ によって誘導された $G(P)$ の部分グラフとし, $m,$ $m’\in S$ とする. このとき, $m$ と $m’$ を結ぶ

道が $G(S)$ の中に存在し, 道の中の任意の辺 $\{m’’, m’’’\}$ の色は庫.

$|\exists u\in m\backslash m’\mathrm{s}.\mathrm{t}$$i=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}$$u$} に含まれる.

をみたすときをいう.

補題 24(局所弱上半モジュラーのための必要十分条件 (池辺, 平林 [5])): $(P, \leq)$ を次数付き半順序集合とす
に関して性質 (C) をる. このとき, $(P, \leq)$ が局所弱上半モジュラーであるための必要十分条件は, $G(P)$ が$\mathcal{M}$持つことである.

を次数付き半順序集合とする. $G(P)$ が性質 (C-k) を持つとは, $S\subset\lambda 4(|S|=k)$ と$S_{k}=S(|S_{\mathrm{i}}|=i(1\leq i\leq k))$ が存在して, $G(P)$ は $S_{i}(1\leq i\leq k)$ に関して, 性質 (C) を持つときを$S_{1}\subset s_{2}\subset\cdots\subset$$(P, \leq)$$\mathrm{A}\backslash$ウ.

定理 25(必要十分条件 (平林-池辺 [5])): 次数付き半順序集合 $(P, \leq)$ がシエリング可能であるための必要十分を持つことである.
条件は, $G(P)$ が性質$(C-|\mathcal{M}|)$$G$を辺彩色グラフとする.

$C_{1},$$\ldots,$$c_{k}$$C$

を $G$ のサイクル (単純サイクル) としたとき,

2 色で彩色されてたサイクノレ

で$C=C_{1}\oplus\cdots\oplus C_{k}$となるものが存在するとき $C$ を非本質的なサイクルといい, そうでない場合, $C$ を本質的なサイクノレとだし, $C\oplus C’$ は $C$ と $C’$ の対称差を表すものとする.

$\mathrm{A}\backslash$

う. た

86
定理 26(必要条件 (平林-池辺 [5]))リング可能であれば, $G(P)$$\ovalbox{\tt\small REJECT}(P, \ovalbox{\tt\small REJECT})$を次数付き局所弱上半モジュラー半順序集合とする.

$\Delta(P)$がシェは本質的なサイクルを含まない.

3Dunce hat の正則$\mathrm{C}\mathrm{W}$

分割極大領グラフを用いた順序複体のシェリング

可能性についてこの章では, 定理 26 の逆は成り立たない, すなわち, 極大鎖グラフが本質的サイクルを含まなくても, シェリ
ング可能とはならないことの反例を示すことにする. そのためにまず, Dunce hat を定義する. すなわち, Dunce
hat は, 図 1 のように, 三角形の 3 辺を矢印の方向に同一視したものである [17].
Dunce hat は境界のない可縮である位相空間である. また, Cohen-Macaulay であるが, シェリング可能では

図 1: Dlmce hat
ない 2 次元の単体的複体の例としてよく知られている (Stanley 3.1 を参照). いま, 位相空間 $X$ がある多面体$P=|K|$ と同相であるとき, $X$ を位相多面体といい, 単体的複体 $K$ を $X$ の (位相的) 三角形分割あるいは単体分割という. このとき, 次の定理が成り立つ.

定理 31(Stanley[14]): Dunce hat の任意の三角形分割はシェリング可能ではない.
以下で, Dunce hat の適当な三角分割に対応する極大鎖グラフが本質的サイクルを含まないことを示す. すると,
定理 3.1 によってその三角形分割はシェリング可能ではないので, 定理 26 の逆は成り立たないことがいえる.

なお, 極大鎖グラフのサイクルの列挙は, Tarjan (1975, [11]) による Backtracking Algorithms を用いた.

Dunce hat の三角形分割で, 現在知られている中で, ファセット数が最小なものは 17 ファセットである ([7])
が, この三角形分割に対応する順序複体から誘導される極大鎖グラフに含まれるサイクルの数は, コンピュータの記憶容量をはるかに上回るので, まず, 極大鎖グラフを小さくする工夫が必要とされる. そのために, 正則 CW
分割を用いてファセットの数を減少させることにする.
複体 ([2]) を次のように帰納的に定義する :Hausdorf 空間中の正則は正則分割である.
が点の集合であるとき,$K^{:-1}$ がが K\leftrightarrow のいくっ
$i-1$ 次元の正則複体であるとき, いくつかの 次元球体 を の境界
かの要素の和になるように同相写像によって張り合わせたものをは正則複体である.
としたとき,
図 2 の dunce hat の 6 つのファセットへの分割が正則分割であることを見るためには, 各ファセットを重心細分をしたとき, 全体が単体的複体になっていればよいが, 実際に重心細分をしてみると図 2 のとなって, 単体的複体となっていることが分かるので, この 6 つのファセットに分割したものは正則分割である. ここで$\mathrm{C}\mathrm{W}$$\bullet$$\bullet$$K^{0}$$K^{0}$$\mathrm{C}\mathrm{W}$$i$$\mathrm{C}\mathrm{W}$$\sigma$$K^{:}$$\sigma$$\sigma$$K^{:}$$\mathrm{C}\mathrm{W}$$\mathrm{C}\mathrm{W}$$\mathrm{C}\mathrm{W}$87

6 つ極大面を重心細分した図6 つの極大面に
正則 CW 分割した図

図 2: Dunce hat の正則$\mathrm{C}\mathrm{W}$

分割と順番に並べたとき, 次の条件
複体 $K$ のシェリングの定義を述べる. $K$ のファセットを
複体 $K$ はシエリング可能であるという :をみたせば, この順序ををシェリングといい,

正則$\mathrm{C}\mathrm{W}$$\sigma_{1},$$\sigma_{2\cdots,t},\sigma$$\mathrm{C}\mathrm{W}$(1) $t=1$ であるとき, $K$ はシエリング可能である.
, $(2\leq t)$ は極大面の次元がすべて $\dim\sigma j-1$ となる.
$\sigma j-1>$ 口(2)(3)$<\sigma_{1},$$\sigma_{2},$$<\sigma 1,$$\sigma 2,$$\sigma j$$\ldots,$$\sigma j-1>\cap\sigma_{j},$$\ldots,$$(2\leq t)$

はシエリングをもち, それを

命題 32. Dunce hat の 6 つのファセットに正則 CW 分割した$\sigma j$$\Delta$に拡張できる.

は, シエリング可能ではない.

証明: $F_{1}=\{1,2,3\},$ $F_{2}=\{1,2,3\},$ $F_{3}=\{1,2,3\},$ $F_{4}=\{1,2,3\},$ $F_{5}=\{1,2,3\},$ $F_{6}=\{1,2,3\}$ とする (図 2 左のはシェリング可能ではないことを以下で示す.
ように, 極大面の名前をつける). このとき,のいずれを並べてもシェリングとならない.
の後に$\Delta$$F_{2},$ $F_{3},$ $F_{4},$$F_{1},$ $F_{6},$$\ldots$$F_{1},$$\ldots$の場合:

こ$F_{5}$の場合をまず考える.

(1) この後に$F_{2}$となり, これは$F_{2}$のファセットによって生成を並べると $<F_{1},$ $F_{6}>\cap<F_{3}>=\{1,2,3, e_{1}\}$ となり, これは$F_{3}$のファセットによって生或を並べると$<F_{1},$ $F_{6}>\cap<F_{2}>=\{1,2,3, e_{4}\}$

されない.

(2) この後に$F_{3}$されない.

(3) この後にとなり, これは$F_{4}$

を並べると$F_{5}$

を並べると $<F_{1},$ $F_{6}>\cap<F_{5}>=\{1,2,3, e_{8}\}$ となり, これは$<F_{1},$ $F_{6}>\cap<F_{4}>=\{1,2,3\}$$F_{4}$のファセットによって生成されない.

(4) この後に$F_{5}$のファセットによって生成

されない.

同様に,
性によって,$F_{2},$$\ldots,$$F_{5}$の次に並べてもシエリングとならないことがわかる. すると, 議論の対称のいずれを最初にしてもシェリングとならないことがわかる.

のいずれを$F_{1}$$\bullet$$F_{2},$$\ldots,$$F_{6}$

分割
分割したは, シエリング可能ではないので, この正則
Dunce hat を 6 つのファセットに正則
分割からはシェリング可能ではないことがわかる [3]. Duunce hat の正則から誘導される順序集合の局所弱上半モジュラー池辺[6]は局所弱上半モジュラー半順序集合であることは,誘導される順序集合
判定プログラムを用いて確認をした.
$\mathrm{C}\mathrm{W}$$P(\Delta)$$P(\Delta)$$\mathrm{C}\mathrm{W}$$\Delta$$\mathrm{C}\mathrm{W}$881

図 3: 正則$\mathrm{C}\mathrm{W}$

分割から誘導される半順序集合のハッセ図

図 3 の半順序集合は 36 の極大鎖を含んでいるので, その極大鎖グラフ $G(P)$ の頂点は 36 となる (極大鎖リスト及び極大鎖グラフは付録

4$\mathrm{B}$を参照).

極大領グラフが本質的サイクルを含まないことの効率的な判定法
本節では, 極大鎖グラフ $G(P)$ が本質的サイクルを含むかどぅがを効率的に判定するための定理を証明する.

まず, 次の初等的な事実のいくつかを確認しておく.
補題 4.1. $G(P)$ の基本サイクル集合$C$に含まれる基本サイクルの中で本質的サイクルが存在する場合には,$G(P)$ は本質的サイクルを含む.

補題 42. $G(P)$ の基本サイクル集合$i=1,2,$れたサイクノ各$c_{\dot{l}}\in C,$$k$$\ldots,$$\mathrm{s}c_{\dot{l}1},$$\ldots,$$C$に含まれる基本サイクルの中に本質的サイクルが存在しない場合には,は 2 色で彩色されたサイクルの対称差で表すことができる.

$c_{\dot{\iota}j}.\cdot$が存在して$c.\cdot=C.\cdot 1\oplus\cdots\oplus C.\cdot j$

すなゎち, 2 色で彩色さ: となる.

(証明) 本質的サイクルの定義から明らか.

$\bullet$

これより, 次の命題がいえる.
命題 43.
(証明)

$C$

$C$

のすべての基本サイクルが本質的サイクルでない場合, $G(P)$ は本質的サイクルを含まない.

を $G(P)$ の任意のサイクルとすると, 補題 42 より$C_{1},$$\ldots,$$C_{\ell}\in C,$$(\ell\leq k)$

が存在して

.

$C=.\oplus c.\cdot=.\oplus\oplus c_{\mathrm{j}}|=1\ell\ell j_{l}|=1j=1^{\cdot}$と表すことができる. したがって, $C$ は本質的サイクルではない.

$\bullet$

上の命題 $G(P)$ に本質的サイクルが存在するかどうかを判定する, 実際的なアルゴリズムを次のように構築することができる.

(アルゴリズム)

89$1^{\mathrm{o}}G(P)$の全張木 $T$ を 1 つ選んで固定する. $T$ に対応する $G(P)$ の基本サイクルの基底を求め, $C=\{C_{1}, \ldots, C_{k}\}$とする.

に対して, 以下のことを繰り返す.
が本質的サイクルかどうかを判定する. 本質的サイクルであれば終了する. このとき, $G(P)$ は本質的サイク$2^{\mathrm{o}}i=1,$$C_{i}$$k$$\ldots,$

ルを持つことになる.
$3^{\mathrm{o}}G(P)$は本質的サイクルを持たない.

によって生成される $G(P)$と分割し,次に, $G(P)=(V, E)$ と表すことにし, $V=V_{1}\cup V_{2},$$e\in
E|\existsu\in
V_{1},$
such that $e=\{u,$ }( , E2) とお .の部分グラフをそれぞれ $G_{1}(V_{1}, E_{1}),${の枝はすべて同一色で塗られているものと仮定する.
とする. 以下では,と $v’,$ をの道$e’=\{u’,v’\}\in\tilde{E},$$(u, u\in V_{1}, v, v’\in V_{2})$ 力\tilde 強同値であるとは, $u,$ $u’$ を結ぶ$e=\{u, v\},$の道が存在して, サイクル $(u, P_{1}, u’, e’, v’, P_{2}, v, e, u)$ が 2 色以下で彩色されているときをいうもの
結ぶが存在して,
が同値であることを,と書くことにする. また,とする. このとき,$V_{1}\cap V_{2}=\emptyset$$G_{2}$$\langle$$V_{2}$$V_{2}$$V_{1},$$\tilde{E}=$$v\}$$\exists v\in V_{2}$$\tilde{E}$$G_{1}$$G_{2}$$P_{1}$$v$$P_{2}$$e\sim^{l}e’$$e\sim e_{1}’,$$e_{1}\sim^{l}e_{2},$$\ldots,$$e,$$e’\in\tilde{E}$$e_{1},$$e_{k}\in\tilde{E}$$\ldots,$$ek\sim’e’$が成り立つとこをいうものとする. このとき, $e\sim e’$ と書くことにする. このとき, 明らかに$\sim$

は$\tilde{E}$上の同値関すべて同一色の枝で連結

図 4: 同値係である.

に関する同値の同値関係
定理 44. $G(P)$ の部分グラフ $G_{1}(V_{1}E_{1}),$ $G_{2}(V_{2}, E_{2})$ がそれぞれ連結とし,でぬられているものとする. このとき,のすべての枝が色であるものとする. また,類がただ一つ$\tilde{E}$$G_{1}(V_{1}E_{1}),$

証明 :

$C$

$G_{2}$($V_{2}$$\sim$$\tilde{E}$$\tilde{E}$$\alpha$, E2) のいすれも本質的サイクルを含なければ, $G(V, E)$ も本質的サイクルを含まない.

を $G(P)$ の本質的サイクルとする.

$C\subset G_{1}(V_{1}, E_{1})$あるいは $C\subset G_{2}$ ($V_{2}$, E2) であれば

$G_{1},$ $G_{2}$が本

質的サイクルを含まないとする仮定に矛盾する.
( , E2) のいずれにも含まれない場合を考える. このと次に, 本質的サイクル $C$ が部分グラフとする. このとき, 仮定の要素となっているものは偶数本であるから, それらをき, $C$ の枝で,が存在して,,
からはすべて同値である. すると,
$G_{1}(V_{1}, E_{1}),$ $G_{2}$$V_{2}$$\tilde{E}$$e_{1},$$\ldots,$$e_{1},$$e_{1}’,$$e_{2k}$’$e_{1}\sim$e_{\acute{\ell}}\sim^{l}\prime\prime\prime$e_{1},$ $e_{1}\sim e_{2}’,$ $\ldots,$$\ldots$$C_{1},$$\ldots,$$C_{\ell},$$C_{\ell+1}$

で$E(C_{\ell})\cap\tilde{E}=\{e_{\acute{\ell}-1}, e_{\acute{\ell}}\},$ $E(C_{\ell+1})\cap\tilde{E}=$$\ldots,$$\ldots,$e2となる. すると, 2 色以下で塗られたサイクル$E(C_{1})\cap\tilde{E}=\{e_{1}, e_{1}’\},$$e_{2},$$e\text{》}\in\overline{E}${$e_{\acute{\ell}}$, e2}$e_{2k}$90をみたすものが存在する. ただし, $E(C_{j}’)$ は $C$ の枝集合を表すものとする. このとき,$C\oplus C_{1}\oplus C_{2}\cdots\oplus C_{\ell+1}$を考えると, これはいくつかのサイクルからなることになるので, その中の少なくとも 1 っは本質的サイクルを含むことになる. それをとすると,{e2, . . . , } となる.
$C^{1}\cap\tilde{E}\subset$$C^{1}$

高々$k$$e_{2k}$

回上の手続きを繰り返すことによって,$G_{1}(V_{1}, E_{1}),$ $G_{2}(V_{2}, b)$のいずれかに含まれる本質的サイクルがえられることになる. これは, $G_{1}(V_{1}, E_{1}),$ $G_{2}(V_{2}, b)$ のいずれも本質的サイクルを含まないということに矛盾する.

5$\bullet$Dunce hat の正則 CW 分割から誘導される極大曽グラフが本質的サイクルを含まないことの証明

Dunce hat の正則
分割から誘導される極大鎖グラフが本質的サイクルを含まないことは, 全張木がら誘
導される基本サイクル集合を用いたアルゴリズムを用いても証明されるが (基本サイクル数:25, 内, 2 色のサイ
クル数:5, 3 色のサイクル数:20) , ここでは定理 4.4 を用いて証明する. すなわち, 極大鎖グラフ $G(P)$ が 6 っの
6 角形のサイクルの連結部分が同一色の枝で連結されてぃることを利用して証明する. まず, $G(P)$ を図時すると図 5 となる. 図中で, 6 角形間を結んでいる辺はすべて同一色緑で彩色されており, 6 角形の内部の辺の内, 実$\mathrm{C}\mathrm{W}$

図 5: 極大鎖グラフ $G(P)$線で表されている辺は青, 点線で表されている辺は赤で彩色されているものとする.
定理 51. Dunce hat の正則$\mathrm{C}\mathrm{W}$

分解から誘導される順序集合 $P$ を考え, その極大鎖グラフを $G(P)$ とする. す

ると, $G(P)$ は本質的サイクルを含まない.
証明: Dunce hat の正則$\mathrm{C}\mathrm{W}$

分解から誘導される順序集合 $P$ を考え, その極大鎖グラフを $G(P)$ とする. このとき,$V=\{v_{1}, \ldots, v_{36}\}$である.

いま, $V:=\{v_{1}, \ldots, v_{12}, v_{13}, \ldots, v_{36}\},$ $V_{2}:=\{v_{13}, \ldots, v_{18}\}$ とし, $G_{1}=(V_{1}, E_{1}),$ $G_{2}=(V_{2}, \ )$ をそれぞれ$V_{1},$$V_{2}$から誘導される誘導部分グラフとする. すると,$\tilde{E}_{1}$$=${$e_{1}=\{1,13\}$, e2 $=\{3,15\},$ $e_{3}=\{8,14\},$ $e_{4}=\{12,17\},$ $e_{5}=\{13,31\}$ ,$e_{6}=\{15,33\},$ $e_{7}=\{16,22\},$ $e_{8}=\{18,23\}\}$

91縁$v_{1}e_{1,arrow}$縁$v_{15}$$v_{13}65,arrow$$v_{16}e_{7,arrow}$縁$v_{15}$, 緑縁\rightarrow$v_{31}e_{5,arrow}$縁赤$v_{22}67,arrow$$v_{21}$

縁赤縁$v_{16}$$\Rightarrow$$e_{7}\sim’ e_{8}$,$v_{13}$$\Rightarrow$$e_{1}\sim’ e_{5}$,$\Rightarrow$$e_{6}\sim’ e_{7}$,$\Rightarrow$$e_{4}\sim’ e_{8}$赤$v_{29}$$v_{30}$縁$v_{23}e_{8,arrow}$$v_{24}$,$v_{5}$$v_{6}$$v_{36}$赤$e_{5}\sim’ e_{6}$

赤縁$v_{35}$縁$v_{13}$$v_{15}$$v_{16}$$v_{11}$

赤,$\Rightarrow$赤縁$v_{12}$$e_{3}\sim’ e_{4}$$v_{27}$$v_{28}$$v_{34}$

縁$\Rightarrow$

赤

縁

赤

$v_{14}$縁$v_{1}$$v_{33}$$v_{17}e_{4,arrow}$$v_{18}$縁$v_{13}e_{1,arrow}$,青$v_{23}e_{8,arrow}$$v_{22}$$\mathrm{e}_{6}$$v_{15}$縁青$e_{1}\sim’ e_{2}$青$v_{33}e_{6,arrow}$$v_{31}$縁$v_{17}$

縁青$\Rightarrow$$v_{1}$

青$v_{12}e_{4,arrow}$$v_{8}$

縁青$v_{3}$

縁青$v_{14}\mathrm{e}_{3,arrow}$

e2, 縁

青
$v_{13}$赤$v_{18}$$v_{17}$であるから, $[e_{1}]=$ { , e2,} である. した力\tilde って, $G(P)$ に本質的サイクノレカ\tilde あるかどうかのはのいすれにも本質的サイクルがなければ, $G(P)$ には本質的サイクルがないことがわかる.
判定はについて考える.
2 色で塗られているサイクルであるから, 本質的サイクルを含まない. そこで,
$V_{3}=\{v_{1}, \ldots, v_{6}, v_{25}, \ldots, v_{36}\},$ $V_{4}=\{v_{7}, \ldots, v_{12}, v_{19}, \ldots, v_{24}\}$とし, $G_{3}=(V_{3}, E_{3}),$ $G_{4}=(V_{4}, E_{4})$ をそれぞ$e_{6},$ $e_{7},$$e_{5},$$e_{3},$ $e_{4},$$e_{1}$$e_{8}$$G_{2}$$G_{1},$ $G_{2}$$G_{1}$

れ$V_{3}$,から誘導される誘導部分グラフとする. すると,

$V_{4}$$\tilde{E}_{2}$$=$$e_{9}=\{4,10\},$ $e_{10}=\{6,11\},$ $e_{11}=\{7,25\},$ $e_{12}=\{9,27\},$ $e_{13}=\{19,25\}$

$\{$

,

$e_{14}=\{21,27\},$ $e_{15}=\{20,26\},$ $e_{16}=\{24,29\}\}$

である. すると,
縁,縁$v_{19}e_{13arrow}$,縁$v_{20}e_{15arrow}$$v_{27}e_{10arrow}$$v_{25}$’縁$v_{10}611arrow$,緑青$v_{7}\mathrm{e}_{9,arrow}$,縁青$v_{6}e_{12arrow}$$v_{4}$

青,縁$v_{27}e_{14arrow}$青,縁$v_{29}e_{16arrow}$$v_{25}$$v_{26}$

縁 $v_{25}e_{13arrow}$赤縁$v_{28}$,縁$v_{19}e_{13arrow}$赤,縁$v_{27}e_{14arrow}$赤$v_{25}$$v_{21}$$v_{24}$$e_{11}\sim’ e_{12}$,$v_{19}$$\Rightarrow$$e_{13}\sim’ e_{14}$,$v_{20}$$\Rightarrow$$e_{15}\sim’ e_{16}$,$\Rightarrow$$e_{9}\sim’ e_{13}$$v_{10}$$\Rightarrow$$e_{11}\sim’ e_{14}$$v_{19}$$\Rightarrow$$e_{13}\sim’ e_{15}$縁$v_{19}$$v_{7}$,

赤$v_{34}$$v_{33}$赤$v_{9}$,縁$v_{26}e_{16arrow}$$\Rightarrow$青縁$v_{21}$$v_{10}$青縁$v_{3}$$v_{4}$$e_{9}\sim’ e_{10}$青$v_{11}$,$\Rightarrow$$v_{7}$,縁$v_{7}e_{9,arrow}$,縁$v_{10}e_{10arrow}$青$v_{9}$

赤$v_{20}$,であるから, $[e_{9}]=\{e_{9}, e_{10}, e_{11}, e_{12}, e_{13}, e_{14}, e_{15}, e_{16}\}$ である. したがって, $G(P)$ に本質的サイクノレカ\tilde ないかどにつのいずれにも本質的サイクルがないかどうかを判定すればよいことがわかる.
うかの判定は
力 らて考える. $V_{5}=\{v_{7}, \ldots, v_{12}\},$ $V_{6}=\{v_{19}, \ldots, v_{24}\}$ とし, $G_{5}=(V_{5}, E_{5}),$ $G_{6}=(V_{6}, E_{6})$ をそれぞれ$G_{3},$$G_{4}$$G_{4}$$\mathrm{A}\backslash$$\backslash$$V_{5},$$V_{6}$

誘導される誘導部分グラフとする. すると,$\tilde{E}_{3}=\{e_{17}=\{7,19\}, e_{18}=\{9,21\}\}$

である. このとき,,

a$\text{縁v_{21}e_{17},$}\# e_{18arrow}$$v_{7}arrow v_{19}arrow$v_{9}arrow v_{7}\yen$$\Rightarrow$$e_{17}\sim’e_{18}$のに本質的サイクルがな ‘かどうかの判定はのいずれも 2 色で彩色されてずれにも本質的サイクルがないかどうかを判定すればよいことがわかる.

であるから, $[e_{17}]=\{e_{17}, e_{18}\}$ である. したがって,$\mathrm{A}$$G_{4}$$G_{5},$

いるサイクルであるから, 本質的サイクルではない.

$G_{6}$$G_{5},$ $G_{6}$$\mathrm{A}\backslash$92$G_{3}$$\ovalbox{\tt\small REJECT},$に 9‘ゝて考える.
$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\{v_{\mathfrak{b}}\ldots.v_{6}\},$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\{v_{25}\ldots..v_{36}\}$とし,.

$G_{7}\ovalbox{\tt\small REJECT}(\ovalbox{\tt\small REJECT}.E_{7})$から誘導される誘導部分グラフとする. すると,

$G_{8}\ovalbox{\tt\small REJECT}(\ovalbox{\tt\small REJECT},$$E\ovalbox{\tt\small REJECT}$をそれぞれ$\tilde{E}_{4}=\{e_{19}=\{1,31\},e_{20}=\{3,33\}, e_{21}=\{2,32\},e_{22}=\{5,35\}\}$

である. すると,’縁$v_{1}619arrow$青$v_{31}$$\text{縁}v_{32}$$v_{2}e_{21arrow},$,縁$v_{1}e_{19arrow}$青赤$v_{31}$,縁$v_{33}e_{20arrow}$青$v_{3}$$\text{縁}arrow v_{5}$$v_{35}e_{22},$$\text{縁}arrow v_{2}$$v_{32}e_{21},$$v_{1}$$\Rightarrow$$e_{19}\sim’ e_{20}$,$\Rightarrow$$e_{21}\sim’e_{22}$,$\Rightarrow$$e_{19}\sim’ e_{21}$青$v_{2}$

赤$v_{1}$

であるから, $[e_{19}]=\{e_{19}, e_{20}, e_{21}, e_{22}\}$ である. したがって,に本質的サイクルがないかどぅかの判定はのいずれにも本質的サイクルがないかどうかを判定すればよいことがわかる.
は 2 色で塗られてぃるサイク
ルであるから, 本質的サイクルを含まない.
に いて考える. $V_{9}=\{v_{25}, \ldots, v_{30}\},$ $V_{10}=\{v_{31}, \ldots, v_{36}\}$ とし, $G_{9}=(V_{9}, \mathrm{R}),$$G_{5}$$G_{7},$ $G_{8}$$G_{7}$$G_{8}$$-\supset$$G_{10}$をそれぞれ$=(V_{10}, E_{10})$$V_{9},$$V_{10}$から誘導される誘導部分グラフとする. すると,$\tilde{E}_{5}=\{e_{23}=\{28,34\},e_{24}=\{30,36\}\}$

である. すると,,$v_{28}$

縁句$arrow 3$青$v_{34}$,縁$v_{36}arrow e_{24}$青$v_{30}$$v_{28}$$\Rightarrow$であるから, $[e_{23}]=\{e_{23}, e_{24}\}$ である. , たがって,$e_{23}\sim’e_{24}$のいに本質的サイクルがないがどぅかの判定はずれにも本質的サイクルがないかどうかを判定すればよいことがわかる.
は何れも 2 色で塗られてぃる
サイクルであるから, 本質的サイクルを含まない.
以上のことから, $G(P)$ は本質的サイクルを含まないことが証明された.
$|$$G_{8}$$G_{9},$ $G_{10}$$G_{9},$ $G_{10}$$\bullet$謝辞

八森正泰博士には, 終始適切なコメントをいただき, 深く感謝致します. 彼のコメントがなければ, 本研究は成就しなかったものとおもわれます.

参考文献[1] Bj\"omer, A.: “SheUable and Cohen-Macaulay partially ordered sets.” Tans. Amer. Math. Soc., 260, pp.159
183,(1980).
[2] Bj\"orner,

mathO&,in “HandBook of Combinatrioe”,(R.Graham,M.Gr\"otschel and L.Lov\’asz),-Holland,$\mathrm{A}.:\mathrm{T}\circ \mathrm{p}\circ \mathrm{l}\circ \mathrm{g}\mathrm{c}\mathrm{a}\mathrm{l}$$\mathrm{e}\mathrm{d}\mathrm{s}.$$\mathrm{p}\mathrm{p}.$$No\hslash h$

181&1872,(1995).

[3] Bj\"orner, A.: “complexes and Bruhat order” ,Europ. $\omega mbinatorics$ , 5, PP. 7-16, (1984).
$\mathrm{P}\mathrm{o}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{s},\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{C}\mathrm{W}$[4] 平林隆一, 池辺淑子: 「代数的組合せ論 -順序集合のホモロジー」 ,manuscript,(200).
[5] 平林 $\ ^{-}$ , 池辺淑子:「順序複体のシェリング可能性について」[6] 池辺淑子: 「局所弱上半モジュラー半順序集合判定プログラム」,yosh 債 \copyright ms. kagu . $sut.a$ c.jP, 東京理科大学工学部経営工\yen R 所属,(1997).
$\mathit{0}$93[7] M 下 sahiro Hachimori: “Combinatorics ofUniversity of TOkyO,(2000).
Doctorial$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\ovalbox{\tt\small REJECT} \mathrm{b}\mathrm{l}\mathrm{e}$Complexes”,$Thesis,\mathrm{t}\mathrm{h}\mathrm{e}$[8] Masahiro Hachimori: 「複体の組合せ論入門」 ,$http.\cdot//www$ .qci.jst.go $.jp/\sim hachi$ ,(2001).
[9] Masahiro Hachimori: 「種々の二次元の単体的複体の例」 , ゼミ資料,(8.10.1998).

[10] Peter Kleminschmidt and Shmuel Onn: “Signable posets and partitionable simplicial complexes”,Discrete
Comput. Geom. ,15,PP.7I8-755,(I996).
[11]: “Bounds on Backtrack Algorithms for Listing
Trees” ,Networks, 5,PP. 237-252,(1975).

$\mathrm{C}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{s},\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{s},\mathrm{a}\mathrm{n}\mathrm{d}$$\mathrm{R}.\mathrm{C}.\mathrm{R}\mathrm{e}\mathrm{a}\mathrm{d},\mathrm{R}.\mathrm{E}.\mathrm{T}\mathrm{a}\mathrm{r}\mathrm{j}\mathrm{a}\mathrm{n}$Spanning[12] Stanley, R., ”Cohen-Macaulay rings and constructible polytopes,” Bull. Amer. Math. Soc., 81, pp.135142,(1975).

[13] Stanley, R., ”The Upper Bound Conjecture and Cohen-Macaulay rings,” Studies in Applied Math.,
54,pp.l35-l42,(l975).
[14] Richard P.Stanley:”Combinatorics and Commutative Algebra,
Second Editi0n”,Birkh\"auser,(1996).
[15] Richard P.Stanley (著) , 成鳩弘 (訳) :, 「数え上げ組合せ論 」, 日本評論社,(1990).
$\mathrm{I}$[16] W.Bruns and J.Herzog:” Cohen-Macaulay Rings” ,Cambridge University Press(1993).

[17]$\mathrm{E}.\mathrm{C}.\mathrm{Z}\mathrm{e}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{n}:$”$\mathrm{O}\mathrm{n}$the dunce hat” ,Topology,2,PP.341-358,(1964).