7.f-列、h-列とM-列：単体的複体の理論へ

6章では、という集合族を考え、 それが部分集合に閉じている、すなわち、単体的複体であるということから、 スペルナーの定理を用いてネットワーク信頼度の上下限を与えることができることを見た。 このときに、F_iをに属するサイズiの要素の個数とした。 そして、(F₀, F₁, ..., F_m)の上下限を見積もることで、ネットワーク信頼度の上下限を与えた。

単体的複体の言葉では、サイズiの要素は「i−1次元の面」と呼ばれ、 i次元の面の個数をf_iと表す。つまり、F_i＝f_i-1となる。そして、(f_-1, f₀, ..., f_d)は「f-列」と呼ばれる。 ここで、dは単体的複体に含まれる面の最大の次元のことである。 上の言葉では、F_k≠0な最大のkに対して、d＝k−1ということになる。

単体的複体に関する理論においては、f-列と関連して、h-列という概念がある。

f(x)＝ f_-1x^d+1＋f₀x^d＋f₁x^d-1＋…＋f_dx⁰ (＝ F₀x^d+1＋F₁x^d＋F₂x^d-1＋…＋F_d+1x⁰)

という多項式を考え、これに対して、

f(x-1)＝h(x)

となるように多項式h(x)＝ h₀x^d+1＋h₁x^d＋h₂x^d-1＋…＋h_d+1x⁰ を考える。この係数(h₀, h₁, ..., h_d+1)が「h-列」である。

f-列からh-列を得るには、多項式f(x-1)を展開して係数を見ればよく、 逆にh-列からf-列を得るときには、多項式h(x+1)を展開して係数を見ればよい。 直接f-列とh-列を互いに変換するための公式を書き下すことも、 二項係数を用いて簡単にできる。

h-列は単体的複体の性質を調べる上でしばしば重要となるもので、 例えば、凸多面体の面の数に関する上限予想の証明などでクリティカルに用いられている。 また、単体的複体の分割や、可換代数との関連などにおいて重要な役割を果たしている。

このh-列を用いると、ネットワーク信頼度は次のように書き換えられる。

Rel(G)＝F₀p^m(1ーp)⁰＋F₁p^m-1(1ーp)¹＋F₂p^m-2(1ーp)²＋…＋F_mp⁰(1ーp)^m
            ＝ p^m-(d+1)(h₀(1−p)⁰＋h₁(1−p)¹＋…＋h_d+1(1−p)^d+1)

(→ 証明を見る)

したがって、これらのh_iの上限下限からもRel(G)の上下限が分かる。

h-列に関する重要な定理は次のものである。

マコーレーの定理 単体的複体がコーエン・マコーレーであるなら、 そのh-列はM-列である。ここで、M-列とは、次の条件を満たす数列である。 h0＝1 で、各1≦k≦d+1に対して、hi≧0, 各1≦k≦d+1に対して、hk-1≧∂k(hk). 逆に、任意のM-列は、あるコーエン・マコーレーな単体的複体のh-列として生じる。

ただし、ここで、∂^k(n)という特殊な記号を使っているが、これは、 次のようにして定まる数である。 まず、自然数nとkに対して、

n ＝ _akC_k ＋ _ak-1C_k-1 ＋ … _a1C₁

のように、一意にa_k, a_k-1, …, a₁を定めることができる。これを、nの二項展開という。これに対して、

∂^k(n)＝ _ak-1C_k-1 ＋ _ak-1-1C_k-2 ＋ … _a1-1C₀

と定める。 (各項_nC_rのnおよびrから1ずつ引いている。)

(M-列はO-列とも呼ばれる。)

このマコーレーの定理はコーエン・マコーレーな単体的複体のh-列を完全な特徴付けを与えている。(コーエン・マコーレーならh-列は条件をみたし、逆に、条件を満たす列には、それをh-列として持つコーエン・マコーレー単体的複体がある。)

この定理は、単体的複体が「コーエン・マコーレー」という性質を持っている特殊な単体的複体でないと使えないのであるが、 実はネットワーク信頼度の計算に用いるはこの性質を満たしている。 この定理の不等式を用いてネットワーク信頼度の上下限を与えたものが、「スタンレー限界」である。 BBST限界やクルスカル・カトナ限界が一般の単体的複体に対して得られる不等式を用いているのに対し、このスタンレー限界では、の持つ特殊な構造に関する性質を用いており、よりよい上下限を与えることにつながる。

f-列とh-列、M-列、マコーレーの定理についての解説は、

• ギュンター・M・ツィーグラー,「凸多面体の数学」(シュプリンガーフェアラーク東京)
• 日比孝之,「可換代数と組合せ論」(シュプリンガーフェアラーク東京)