組合せ数学の雑記帳 第11回

「シェリングと分割とh-列」

単体的複体のシェラビリティーに関して興味深い構造として、 シェラブルな単体的複体に対してはきれいな分割が与えられる、というものがあります。

例えば下図の左端の単体的複体は、付けてある番号でシェリングになっています。 ここで、このシェリングに沿って単体的複体が組み立てられる様子を考え、各段階で 新しく付け加わる単体の集合ごとにまとめていくと、右側上部のように分割されます。 この図では、単体をその頂点で表していて、「abc」はa,b,cの3つを頂点に持つ三角形 を表しています。 この図は単体的複体の単体(=面)の間に包含関係で順序を入れた半順序集合を表していて、 これはこの単体的複体の面半順序集合と呼ばれます。 ここで得られた分割は、分割を構成するそれぞれの集合が ブール束と呼ばれるものと同型になっています。 つまり、これは、シェリングによって面半順序集合を、ファセットを最大要素とするような ブール束に分割する、ということができたことになるわけです。 右側の下部に書いたのは、この分割の様子を直接単体的複体上に図示してみたものです。 (空集合は図の中に見えないので、明示的に「$\emptyset$」と文字で書き加えています。)

 

この例ではシェラブルな単体的複体においてシェリングから分割がつくられたのですが、 シェリングに関係なく、面半順序集合を同様にファセットを最大要素とするような ブール束に分割することができるとき、その単体的複体は分割可能であるといいます。

単体的複体がシェラブルなら、上で説明した方法により、必ず分割が得られます。 このことから、分割可能という性質はシェラブルという性質より弱い、一般化された性質 ということになります。 シェラブルより弱い性質になっているということは、実際にシェラブルでない単体的複体が 分割可能になることがあり、例えば下図のような例はいずれもシェラブルではないのだけれど 分割ができる例になっています。(右は射影平面の三角形分割で、六角形の外側部分は 同じ名前の頂点同志が同一視されるように張り合わせます。外側にかかれている矢印同志を 張り合わせるという形です。)

 

単体的複体が純、すなわち、ファセットの次元がすべて等しい時、 分割可能な単体的複体は$h$-列というものと極めて密接な関係を持ちます。 単体的複体に対して、まず、$f$-列 $(f_{-1},f_0, \dots, f_d)$というものが、 $f_i$がその単体的複体に含まれる$i$次元の単体の個数として定義されます。 (この単体的複体の次元、つまり、含まれる単体の最大の次元が$d$であるとします。) $f_{-1}$は$-1$次元の単体の個数ですが、これは空集合を指します。 (空集合は1つしかないので、$f_{-1}=1$です。) そして、これを用いて、 $$ h_i = \sum_{j=0}^{i} (-1)^{i-j} \binom{d+1-j}{d+1-i} f_{j-1} $$ という式により、$(h_0, h_1, \dots, h_{d+1})$ が定まります。これが$h$-列です。

純な単体的複体が分割可能な時、この$h$-列はこの分割に関して重要な意味を持ちます。 実は、$h_i$は分割において、最小要素になる単体の次元が$i-1$であるようなブール束の 個数に一致するのです。

これは、なぜかというと、ブール束で分割された様子を下図のように図示すると、 $i-1$次元の単体の個数である$f_{i-1}$は $$ f_{i-1} = \sum_{j=0}^{i} \binom{d+1-j}{d+1-i} h_j $$ のように計算される(ブール束の各段の要素数が二項係数で計算できることを使います)の ですが、これは$(f_{-1},f_0,\dots,f_d)$から$(h_0,h_1,\dots,h_{d+1})$への 正則な一次変換になっていて、この逆変換を計算すると上の$h$-列の定義式そのものに なるためです。

このように、$h$-列は分割可能性を調べる上でとても大切な量なのですが、この定義式で 計算するのはちょっと面倒です。しかし、これは簡単な計算法が知られています。

例えば下図の左側の単体的複体に対して計算したいときは、まず、$f$-列を計算します。 この場合、空集合が1個、頂点が4個、辺が5個、三角形が2個あるので、 $f=(1,4,5,2)$です。 ここから$h$-列を計算するのですが、図で単体的複体の下に書いてあるように、 まずこの$f$-列の数字を斜めに並べ、一番上の「1」から右下に向けて「1」を並べ行きます。 あとは、上から順に、「右上-左上」の計算結果を埋めていきます。 (例えば、3段目の真ん中にある「3」は「4-1」の計算結果になっています。) これで最下部に出てくる列が$h$-列になります。 この例の場合、$h=(1,1,0,0)$です。

 

この計算方法はStanleyのトリックと呼ばれているのですが、$h$-列の計算法としてとても有用です。 例えば上図の右側で同様に計算すると、$h=(1,2,-1,0)$という結果がすぐに計算できます。

ここで、この右側の例の$h$-列では、$h_2=-1$と、負の数が出てきています。 上の方の説明で、分割可能な単体的複体では、$h$列の各要素は分割に生じるブール束の個数という 意味を持つということを説明していました。 ということは、この$h$-列が負の要素を含んでいてはおかしいということになります。 このことから、この単体的複体は分割可能ではないということが分かるわけです。 この例はファセットが2つしかなく、少し考えれば簡単に分割可能でないことが分かりますが、 もっと複雑な例に対して分割可能か不可能かよく分からないとき、この性質が重要になることは ままあります。 ただし、$h$-列の非負性は分割可能性の必要条件に過ぎず、 $h$-列がすべて非負整数になったからといって分割可能であることにはならないということには 注意が必要です。

この分割可能性との関係で出てくる$h$列の非負性は、コーエン・マコーレーという性質との関係 でも重要です。 コーエン・マコーレーという性質は、単体的複体のホモロジー群を用いた定義、もしくは、 単体的複体に付随する可換環の言葉での定義、によって定められる概念ですが、 実は、コーエン・マコーレーな単体的複体も$h$-列が必ず非負になることが知られています。 (コーエン・マコーレーの場合は、もっと条件が強く、M-列と呼ばれるものになります。)

このことから、「コーエン・マコーレーな単体的複体は分割可能なのではないか?」という予想が されていました。(コーエン・マコーレーな単体的複体は必ず純です。) これは、StanleyとGarsiaによって独立に1979年頃に提示されたとされています。

この予想はこのあたりのトピックの中で有名な未解決問題で、しかし長年未解決だったのですが、 2016年に、Duval, Goeckner, Klivans, Martinが否定的に解決しました。 コーエン・マコーレーではあるけれども分割可能ではないような単体的複体の構成法を示したのでした。

第10回では、同様に1970年代からの未解決予想だったシェラビリティー判定問題のNP-完全性が 解決されたということを紹介していますが、このあたりの1970~80年代頃からの大きい未解決問題 の解決が続き、状況が大きく動いている感じがします。

この回には、この他に、純でない単体的複体の場合の分割可能性の議論はどのようなことになるのか について、少し紹介をしました。この場合、$h$-列はほとんど役に立たないのですが、 $h$-三角行列というものがあり、これはシェラビリティーや、コーエン・マコーレー性の非純な場合への 拡張である順次コーエン・マコーレー性との相性はよいことが示されているのですが、 残念ながら分割可能性に関してはうまくいかない、ということを紹介したのでした。

(この最後の純でない場の話は、この連載記事執筆の後に私自身の研究の題材として研究が進んで、 $h$-三角行列との関係がうまく行っているシェラビリティーとうまくない分割可能性との間をつなぐ 部分の構造の少し詳しい状況の理解が少し進展しています。)

戻る

八森正泰
hachi@sk.tsukuba.ac.jp
筑波大学システム情報系 (社会工学域)