カットイデアルのグレブナー基底とその応用
著者
阪本 龍一
学位名
博士（理学）
学位授与機関
関西学院大学
学位授与番号
34504甲第719号
URL
http://hdl.handle.net/10236/00029096
カットイデアルのグレブナー基底とその応用
1
目次
序文 3 第1章 グレブナー基底 5 1.1 単項式順序 . . . 5 1.2 グレブナー基底 . . . 6 1.3 割り算アルゴリズム . . . 7 1.4 ブックバーガーのアルゴリズム . . . 9 1.5 イニシャルイデアルと重み順序 . . . 10 1.6 トーリックイデアル . . . 11 1.7 トーリックイデアルと消去理論 . . . 13 第2章 凸多面体とその三角形分割 15 2.1 凸多面体 . . . 15 2.2 凸多面体の三角形分割 . . . 16 2.3 イニシャル複体 . . . 17 2.4 Ehrhart多項式とh∗多項式 . . . 18 第3章 マルコフ基底とグレブナー基底 21 3.1 分割表 . . . 21 3.2 マルコフ基底 . . . 23 3.3 マルコフ基底とトーリックイデアル . . . 24 第4章 カットイデアル 27 4.1 グラフにまつわる諸定義 . . . 27 4.2 カットイデアル . . . 30 4.3 カットイデアルの既存の結果 . . . 322 目次 第5章 カットイデアルの2次グレブナー基底 35 5.1 サイクルのカットイデアル . . . 35 5.2 辞書式・逆辞書式順序に関するグレブナー基底 . . . 42 5.3 カットイデアルの計算実験 . . . 48 第6章 K2,m のカット多面体のh∗ 多項式 51 6.1 第2種Stirling数とEulerian多項式 . . . 51 6.2 K2,n−2のカット多面体のh∗多項式 . . . 52 参考文献 57
3
序文
配置と呼ばれる特殊な整数行列から作られる代数系であるトーリックイデアルは， Sturmfels [23] によって，凸多面体の正則三角形分割と，ある単項式順序に関するトー リックイデアルのイニシャルイデアルより決まる，イニシャル複体と呼ばれるものに対応 することが示唆されたことにより注目されるようになった．多面体的な問題を代数的な 枠組みによってとらえることができるようになったのである．また，Conti-Traversoは， 整数計画問題からトーリックイデアルを作り出し，グレブナー基底を使用することによっ て，その整数計画問題を解くアルゴリズムを考案した[4]．アルゴリズムの世界では，「計 算が終わるまでの速さ」を主とした研究が盛んであるが，Conti-Traversoが考え出したも のは「計算の速さ」では内点法などのアルゴリズムには分が悪いことが多い．しかし，考 えたい対象からトーリックイデアルを作り出し，そのグレブナー基底を使って問題を解く ことができるという点でトーリックイデアルやグレブナー基底は興味深いものになったの である．その後，Diaconis-Sturmfels [5]は，統計学における分割表の検定という問題に ついて，分割表から配置行列を考え，そのマルコフ基底とトーリックイデアルの生成系が 対応することを示し，検定に利用できることを示した．これら3つの結果から，トーリッ クイデアルのグレブナー基底は盛んに研究が行われるようになった． また，グレブナー基底はそれ自体でも研究の対象として，あるいは解明のための道具と して扱われてきた．グレブナー基底は廣中平祐とBruno Buchbergerにより独立に提唱さ れた．両者の目的は異なっており，廣中は代数多様体の特異点解消のために，Buchberger は多変数の多項式による零次元イデアルを用いた剰余環の具体的な構成のために導入し た．このグレブナー基底は現在でも活発に研究されているが，その目的は代数学的なもの にとどまらず，統計や符号・暗号など，非常に広い範囲に応用できるものとなっている． 2008年にはSturmfels-Sullivantが[25]において，グラフから導かれるトーリックイデア ルが統計学に応用できることに言及し，このイデアルをカットイデアルと名付け，基本的 な結果・予想を述べている．また，同様の手法で定義される凸多面体であるカット多面体 の代数的性質や三角形分割に関連することなどについては，大杉[14]やSullivant [26]な どの研究結果が報告されている．本論文では，以下の2本の単著論文4 序文
1. Ryuichi Sakamoto, Lexicographic and reverse lexicographic quadratic Gr¨obner bases of cut ideals [18].
2. Ryuichi Sakamoto, The h∗-polynomial of the cut polytope of K2,m in the lattice
spanned by its vertices [19].
に基づき，カットイデアルのグレブナー基底やカット多面体の三角形分割の h∗ 多項式に ついて述べる． 第1章では，グレブナー基底とトーリックイデアルを準備し，消去定理を用いたトー リックイデアルの具体的な計算方法等について述べる．第2 章では，凸多面体とその三 角形分割について定義と例を述べ，h∗ 多項式に関する定義や性質を述べる．第3章では， 代数統計の初歩について述べる．これはSturmfels-Sullivantが[25]で言及したカットイ デアルの統計への応用に関して重要な内容である．第 4章では，カットイデアルを定義 し，既存の研究結果や未解決予想について述べる．Sturmfels-Sullivantが言及した統計 学への応用に関してもここで述べる．第5章では，カットイデアルのグレブナー基底につ いての詳しい結果を見る．まずはサイクルのカットイデアルについて，次にトーリックイ デアルの2次グレブナー基底に関する日比孝之の予想の反例，最後に計算実験について述 べる．サイクルのカットイデアルの項では，「サイクルのカットイデアルは2次のグレブ ナー基底をある辞書式順序で持つ」という主張[12]について，この主張の証明が誤りであ ることを述べる．日比予想の項では，「トーリックイデアルが2次グレブナー基底を持つ とき，辞書式か逆辞書式順序のどちらかでも2次グレブナー基底を持つ」という予想の反 例がカットイデアルにおいて存在することを紹介する．計算実験の項では，「そのカット イデアルが2次生成であるが2次グレブナー基底を持たないグラフ」の候補について述べ る．第6章では，完全二部グラフK2,m より導かれるカット多面体のh∗ 多項式について 述べる．完全二部グラフK2,mはグレブナー基底が具体的にかつ良い条件であると判明し ており[20]，標準単項式の数から直接h∗ 多項式を計算できる． 大学院の指導教授である大杉英史教授には，本研究に関して手厚い指導を賜り，さらに 多くの貴重な御意見を頂きました．ここに感謝の意を表し，謝辞とさせていただきます． 2019年12月 阪本 龍一
5
第
1
章
グレブナー基底
この章では，文献[10]の第 1章に基づいてグレブナー基底の定義と既存の結果につい て紹介し，トーリックイデアルなどの定義をする．グレブナー基底はイデアルの生成系で あるが，冗長な元を持っていることもある．その分，「良い」性質を持った生成系となっ ている．流れとしては，1.1節で単項式順序の定義と例を紹介し，1.2節でグレブナー基底 を定義する．そのあと，1.3節で多変数の多項式による割り算を考える．ここで，「グレブ ナー基底を用いて割り算をすることで余りが一意に定まる」ことを見る．次に，1.4節で 生成系からグレブナー基底を計算する方法である，ブックバーガーのアルゴリズムを紹介 し，実際にグレブナー基底計算の具体例を挙げる．次の1.5節では，イニシャルイデアル に関する結果を紹介し，重みベクトルによる単項式順序の定義を紹介する．最後に，1.6 節と1.7節ではトーリックイデアルの定義と既存の結果の紹介，消去定理との関係につい て見る．1.1
単項式順序
体K 上のn変数多項式環K[x] = K[x1, . . . , xn]に対し，Mn をK[x]上のすべての 単項式の集合とする． Definition 1.1. あるMn上の順序<がK[x]の単項式順序であるとは，次の3つの条 件を満たすときに言う． 1. 任意のMnの単項式u, v (u̸= v)に対し，u < vかv < uのどちらかが成り立つ． 2. 単項式u, vがu < vを満たすとき，任意の単項式w ∈ Mn に対し，uw < vwが 成り立つ． 3. 1でないMnの任意の単項式uに対し，1 < uが成り立つ．6 第1章 グレブナー基底 Example 1.2. 単項式u = xa1 1 x a2 2 . . . xann, v = x b1 1 x b2 2 . . . xbnn が n ∑ i=1 ai > n ∑ i=1 bi を満たすとき，u > vとする．また， n ∑ i=1 ai = n ∑ i=1 bi のとき，(a1− b1, a2− b2, . . . , an− bn)を考え， 1. もし最も左にある0でない要素が正であるときu > vとする．この順序<は単項 式順序であり，次数辞書式順序と呼ばれる． 2. もし最も右にある0でない要素が負であるときu > vとする．この順序<は単項 式順序であり，(次数)逆辞書式順序と呼ばれる． 次数辞書式順序の条件のうち，次数を無視した順序を考えると単項式順序になり，この順 序を辞書式順序と言う．
1.2
グレブナー基底
多項式f ∈ K[x]がu1, . . . , ut ∈ Mnを用いてf = a1u1+· · · + atut (0̸= ai ∈ K, 1 ≤ i ≤ t)と表されるとする．また，K[x]上の単項式順序 <を一つ固定しておく．このと き，f の <に関するイニシャル単項式とは，f に現れる単項式のうち<に関して最大 の単項式ui であり，in<(f )と書く．また，f に現れる全ての単項式の集合{u1, . . . , ut} を f の台と言う．次に，K[x] の0 でないイデアル I と K[x] 上の単項式順序 < を考 える．このとき，I の任意の元の< に関するイニシャル単項式で生成されるイデアル⟨in<(f ) | 0 ̸= f ∈ I⟩をI の<に関するイニシャルイデアルと言い，in<(I)と書く．
Definition 1.3. 多項式環K[x]上の単項式順序<を1つ固定する．また，I をK[x]の イデアルとし，G = {g1, . . . , gs} ⊂ I とする．このとき，G が<に関するグレブナー基 底であるとは，{in<(g1), . . . , in<(gs)} が in<(I)の生成系となるときに言う． 多項式環K[x]上のイデアルIに対し，その根基√I を √ I ={f ∈ K[x] | ∃a ∈ N s.t.fa∈ I} と定める．また，単項式u = xa1 1 x a2 2 . . . xann ∈ Mn に対し， √ u = ∏ ai>0 xi とする．
1.3 割り算アルゴリズム 7 Proposition 1.4 ([10], 命題5.5.5). いくつかのMn 上の単項式m1, m2, . . . , ms で生 成されるK[x]上のイデアルI に対して√I = ⟨√m1,√m2, . . . ,√ms⟩が成り立つ． 単項式mについて，√m = mが成り立つときmをスクエアフリーという．この呼び 方はイデアルなどについても共通である．
1.3
割り算アルゴリズム
1変数の多項式の割り算は単純に変数の次数が大きいものから割り算していけば簡単に 計算できた．しかし，多変数の多項式における割り算は1変数のように単純にはいかな い．その計算法を紹介する前に，語句等の準備をする． Theorem 1.5 ([10], 定理1.2.1). 多項式環K[x]上の単項式順序< を一つ固定してお く．多項式f, g1, . . . , gs ∈ K[x]に対し，K[x]の多項式でf = f1g1+· · · + fsgs+ f′ を 満たすようなf1, . . . , fs, f′ が存在して，次の条件を満たす． 1. f′ ̸= 0であるとき，どのi ∈ {1, 2, . . . , s}についても，f′ の台に属する単項式は in<(gi)で割り切れない． 2. fi ̸= 0であるとき，in<(f )≥ in<(figi)である． Theorem 1.5内のf = f1g1+· · · + fsgs+ f′という表現をf の標準表示と言い，f′を f のg1, . . . , gsに関する余りと言う．これで語句の準備はできたので，多変数の多項式の 割り算アルゴリズムについて紹介する．I をin<(g1), . . . , in<(gs)で生成されるイデアル であるとする． (割り算アルゴリズム) 1. f の台に現れるどの単項式もI に属さないとき，fi = 0, f′ = f とすれば標準表示 を得ることができる． 2. f の台に現れるいくつかの単項式がI に属するとき， u0 をf の台に現れる単項式 のうち<に関して最大の単項式とする．もしu0を割り切るin<(gi)が存在するな ら，それをin<(gi0)，そしてw0 = u0/in<(gi0)とし，f = c0 ′c−1 i0 w0gi0 + h1とお く．ただし，c′0 はf におけるu0 の係数，ci0 はgi0 におけるin<(gi0)の係数であ る．もしu0 を割り切るin<(gi)が存在しないなら，f = h1+ f′ とする．ただし， h1 = f − c′0u0, f′ = c′0u0である． 3. h1 の台に現れるいくつかの単項式がI に属するとき，u1 をh1 の台に現れる単項 式のうち<に関して最大の単項式とする．もしu1 を割り切るin<(gi)が存在する なら，それをin<(gi1)，そしてw1 = u1/in<(gi1)とし，f = c1 ′c−1 i1 w1gi1 + h2 と8 第1章 グレブナー基底 おく．ただし，c′1はh1におけるu1の係数，ci1 はgi1 におけるin<(gi1)の係数で ある．もしu1 を割り切る in<(gi)が存在しないなら，f = h2 + f′ とする．ただ し，h2 = h1− (c′0u0+ c′1u1), f′ = c′0u0+ c′1u1である． 4. これらの操作を，ukに該当する単項式が存在しなくなるまで続ける． Lemma 1.6 ([10], 補題1.2.3). 多項式環K[x] 上の単項式順序<を一つ固定し，G = {g1, g2, . . . , gs}とする．また，I =⟨g1, g2, . . . , gs⟩をK[x]のイデアルであるとする．こ のとき，GがI の<に関するグレブナー基底であるならば，0でない多項式f ∈ K[x]を G で割った余りは一意的である． Corollary 1.7 ([10], 系1.2.4). 多項式環K[x] 上の単項式順序<を一つ固定し，I = ⟨g1, g2, . . . , gs⟩をK[x]のイデアルであるとする．また，G = {g1, . . . , gs} ⊂ I はI の< に関するグレブナー基底であるとする．このとき，0でない任意の多項式f ∈ K[x]がI の元であるための必要十分条件はf のg1, . . . , gsに関する余りが0となることである． もし，f の標準表示を考えたとき，そのg1, g2, . . . , gs に関する余りf′が0と等しくなる ならばf はg1, g2, . . . , gs によって0に簡約されると言う． Definition 1.8. 多項式環K[x]上の単項式順序<を一つ固定し，IをK[x]のイデアル であるとし，G = {g1, g2, . . . , gs}をI の<に関するグレブナー基底であるとする．この とき，Gが極小グレブナー基底であるとは，次の2つの条件を満たすときに言う． • {in<(g1), . . . , in<(gs)}はin<(I)の極小な生成系である． • 各in<(gi) (1≤ i ≤ s)のgi における係数は1である． また，グレブナー基底G = {g1, g2, . . . , gs}が次の2つの条件を満たすときにはG を被 約グレブナー基底と言う． • 異なるi, jに対して，giの台に属する単項式はin<(gj)では割り切れない． • 各in<(gi) (1≤ i ≤ s)のgi における係数は1である． 一般に，K[x] のイデアルI のグレブナー基底 G = {g1, g2, . . . , gs} に0 でない多項式 f ∈ I を加えた集合G′ = {g1, g2, . . . , gs, f}を考えても，G′ はI のグレブナー基底であ る．このように，グレブナー基底は一つに定まらず無数に存在するが，被約グレブナー基 底は一つに定まる． Theorem 1.9 ([10], 定理1.2.5). 多項式環K[x]上の単項式順序<を一つ固定し，I を K[x]のイデアルであるとする．このとき，I の<に関する被約グレブナー基底は一意的 に存在する．
1.4 ブックバーガーのアルゴリズム 9
1.4
ブックバーガーのアルゴリズム
単項式u = xa1 1 x a2 2 . . . xann, v = x b1 1 x b2 2 . . . xbnn ∈ K[x] に対し，ci = max{ai, bi}とす る．このとき，単項式xc1 1 x c2 2 . . . xcnn を最小公倍単項式と言い，lcm(u, v) で表す．次に， K[x]の単項式順序<を一つ固定する．多項式f, g ∈ K[x]に対し，次の式で定義される 多項式S(f, g)をS多項式と言う． S(f, g) = lcm(in<(f ), in<(g)) cf · in<(f ) f − lcm(in<(f ), in<(g)) cg· in<(g) g ただし，cf はf におけるin<(f )の係数，cg はgにおけるin<(g)の係数である． Lemma 1.10 ([10], 補題 1.3.1). 多項式環 K[x] 上の単項式順序 < を一つ固定する． 多項式 f, g ∈ K[x]について，in<(f ) とin<(g) の間に共通な変数が存在しないとき， S(f, g)はf, gによって0に簡約される． Theorem 1.11 ([10], 定理1.3.3). 多項式環 K[x]上の単項式順序 <を一つ固定し，I をK[x]のイデアルであるとする．また，I がG = {g1, g2, . . . , gs} ⊂ K[x]で生成される とする．このとき，GがI の<に関するグレブナー基底であるための必要十分条件は，任 意のf, g ∈ GのS多項式S(f, g)がGによって0へ簡約されることである． (ブックバーガーのアルゴリズム) 多項式環K[x]上の単項式順序<を一つ固定し，I をK[x]のイデアルであるとする．ま た，I がG = {g1, g2, . . . , gs} ⊂ K[x]で生成されるとする．このとき，I の<に関する グレブナー基底は次のように計算できる． 1. Gの多項式gi, gj のS 多項式がGによって0に簡約されるか計算する．もしGの 全ての多項式の組のS多項式が0へ簡約されるなら，アルゴリズムを終了する．こ のとき，GがI の<に関するグレブナー基底である．S多項式が0へ簡約されな いS 多項式がある場合，次のステップへ進む． 2. 0へ簡約されなかったS 多項式のGに関する余りをG に加えG′ とする．この G′ をステップ1におけるGだと考え，もう一度G′のすべてのS多項式をステップ1 と同様に計算する． このアルゴリズムは有限回で終了することが知られている． Example 1.12. 多項式環K[x1, x2, x3, x4, x5]上の単項式順序<を，x1 > x2 > x3 > x4 > x5 より導かれる辞書式順序で固定する．このとき，f1 = x1x3 − x2x4, f2 =10 第1章 グレブナー基底 x2x3− x1x4, f3 = x3x4− x2x5 で生成されるイデアルI =⟨f1, f2, f3⟩のグレブナー基底 を計算する．ここで，G = {f1, f2, f3}としておく． それぞれの先頭項はin<(f1) = x1x3, in<(f2) = x1x4, in<(f3) = x2x5 であり，共通な変 数を持つ先頭項はin<(f1)とin<(f2)なので，Lemma 1.10より計算するべきS 多項式 はS(f1, f2)である．割り算を行う単項式について下線を施すことにする． S(f1, f2) = x4f1+ x3f2 = x2x23− x2x24 より，f4 = x2x23− x2x24,G = {f1, f2, f3, f4}として同様にS多項式を計算する．ここで， in<(f4) = x2x23 である．新たに加わる計算するべきS多項式はS(f1, f4), S(f3, f4)であ る．次に， S(f1, f4) = x2x3f1− x1f4 = x1x2x24− x 2 2x3x4 = x2x4(x1x4− x2x3) =−x2x4f2 S(f3, f4) =−x23f3− x5f4 = x2x24x5− x33x4 =−x42f3+ x3x34− x 3 3x4 よ り ，f5 = x3x34 − x33x4,G = {f1, f2, f3, f4, f5} と し て 同 様 に S 多 項 式 を 計 算 す る ．こ こ で ，in<(f5) = x33x4 で あ る ．新 た に 加 わ る 計 算 す る べ き S 多 項 式 は S(f1, f5), S(f2, f5), S(f4, f5)である．そして， S(f1, f5) = x23x4f1+ x1f5 = x1x3x34− x2x23x 2 4 = x3x24(x1x4− x2x3) =−x3x24f2 S(f2, f5) =−x33f2+ x1f5 = x1x3x34− x2x43 = x 3 4f1+ x2x44− x2x43 = x34f1− x23f4 − x2x23x24+ x2x44 = x34f1− x23f4− x24f4 S(f4, f5) = x3x4f4+ x2f5 = 0 となるので，G = {f1, f2, f3, f4, f5}はI のグレブナー基底となる．
1.5
イニシャルイデアルと重み順序
まずはイニシャルイデアルについての命題をいくつか紹介する． Proposition 1.13 ([10], 命題5.2.1). 多項式環K[x] 上の単項式順序<を一つ固定す る．K[x]上のイデアルI, J がI ̸= J かつ I ⊂ J を満たすとき，in<(I) ̸= in<(J )かつ in<(I) ⊂ in<(J )となる． Proposition 1.14 ([10], 命題5.2.2). 多項式環K[x] 上の単項式順序<, <′ とK[x]上 のイデアルI に対し，in<(I)⊂ in<′(I)⇒ in<(I) = in<′(I)
1.6 トーリックイデアル 11 負の成分を持たないベクトルw = (w1, w2, . . . , wn)∈ Qnを1つ固定する．K[x]の0 でない多項式f を f = m ∑ i=1 cixai(0̸= ci ∈ K) とし，wとの内積が最大になるf の項の和∑icixai をf のイニシャルフォームと言い， inw(f )と書く．このイニシャルフォームにより生成されるイデアルinw(I)を
inw(I) =⟨inw(f ) | 0 ̸= f ∈ I⟩
と定める．一般に，負でない成分から成るQn上の零でないベクトルwとK[x]上の単項 式順序<に対し，<w を以下のように定めると<w は単項式順序となることが知られて いる． 単項式xa, xb ∈ Mnに対し， • w · a > w · b ⇒ xa > w xb • w · a = w · bかつxa > xb ⇒ xa >w xb この順序 <w を重み順序と呼ぶ．さらに，K[x]上のイデアルI と単項式順序<に対し て，I の<に関するイニシャルイデアルには，必ず対応する重み順序が存在することが知 られている． Proposition 1.15 ([10], 命題5.2.7). 任意のK[x]上の単項式順序<と任意のK[x]上 のイデアルI に対して，すべての成分が負でない整数から成るZn上のベクトルwが存 在してin<(I) = inw(I)となる．
1.6
トーリックイデアル
全ての成分が整数である d× n 行列 A = (a1, a2, . . . , an) が配置であるとは，d 次 元の実ベクトル c ∈ Rd が存在して，A の列ベクトルとの内積 ai · c が 1 と等しい ときに言う．整数ベクトル α = (α1, α2, . . . , αd) ∈ Zd に対して，ローラン単項式を tα = tα1 1 t α2 2 . . . t αd d ∈ K[t±11 , t±12 , . . . , t±1d ]と定め，K[A] = K[t a1, ta2, . . . , tan]とする． このK[A]をトーリック環と言う． Definition 1.16. 多項式環K[x]から配置行列Aのトーリック環K[A]への写像π を π : K[x]→ K[A] xi 7→ tai12 第1章 グレブナー基底 を満たす準同型写像とする．この写像π の核を配置行列Aのトーリックイデアルと言い， IAで表す． 一般に，IA は配置行列Aの核に関連付けられた斉次な2項式から生成されることが知 られている [24]．配置行列 Aに対し， KerZA ={b ∈ Zn | Ab = 0}とする．KerZAの 元b = (b1, . . . , bn)に対して， fb = ∏ bi>0 xbi i − ∏ bj<0 x−bj j ∈ K[x] のように多項式を定める． Proposition 1.17. 配置行列 A のトーリックイデアルIA に対して IA = ⟨fb | b ∈ KerZA⟩となる． トーリックイデアルIAに対して，以下の2条件を考える． (1) 多項式環K[x]上の単項式順序<が存在して，<に関するIA のグレブナー基底が 2次の2項式から成る． (2) トーリックイデアルIAは2次生成である． 一般に，(1)⇒ (2)は成り立つが，その逆は成り立たない．これらの条件は，次のような 動機からよく研究されている． • 2次式は列挙しやすく，また，構造がシンプルなため，グレブナー基底を活用した 様々な不変量計算が実行しやすい． (例えば，本研究で成功したカット多面体のh∗多項式の計算はその典型例である．) • 条件(1), (2)はそれぞれ判定が難しい“Koszul”と呼ばれる条件の十分条件，必要 条件となっている． • 重要な性質が“2次の2項式”で表現できる場合がある． (例えば，マトロイドに付随するトーリックイデアルにおける交換関係など．) 固定したK[x]上の単項式順序<を考え，トーリックイデアルの<に関するグレブナー 基底が2次の2項式から成るとするとき，辞書式順序か逆辞書式順序でも同様のことがい える場合が多い．これに関して日比孝之は以下のような予想を提唱した． Conjecture 1.18. あるトーリックイデアルIAに対し，K[x]上の単項式順序<に関す るIA のグレブナー基底が2次の2項式から成るとする．このとき，ある辞書式順序ある いは逆辞書式順序に関するIAのグレブナー基底も2次の2項式から成る． この予想を否定する例を後に定義するカットイデアルと呼ばれるトーリックイデアルの
1.7 トーリックイデアルと消去理論 13 特殊なクラスにおいて発見したので第5章で紹介する．
1.7
トーリックイデアルと消去理論
多項式f ∈ K[x]のうち，変数としてxi1, xi2, . . . , xim のみを持つものを考え，そのよ うな多項式を全て集めた集合をBi1i2...im と表すことにする．明らかにBi1i2...im ⊂ K[x] である．多項式環K[x]上の単項式順序<を一つ固定する．多項式環Bi1i2...im 上の単項 式順序<′を，Bi1i2...imの単項式u, vがK[x]の単項式としてu < vであるときにu <′ v とする．このとき，次の命題が成り立つ． Theorem 1.19 (消去定理). 多項式環K[x] 上の単項式順序<を一つ固定する．また， I を(0)でないK[x]のイデアルであるとし，Gを単項式順序<に関するI のグレブナー 基底であるとする．このとき， g∈ G, in<(g)∈ Bi1i2...im ⇒ g ∈ Bi1i2...im という条件をみたすなら，G ∩ Bi1i2...im はI∩ Bi1i2...im の<に関するグレブナー基底で ある． また，1≤ p < nなるpに対して，B≥pをK[x]の多項式で変数としてxp, xp+1, . . . , xn のみを持つもの全ての集合とする．このとき，消去定理から次が成り立つ． Lemma 1.20 ([10], 系1.4.2). 多項式環K[x]上の辞書式順序<を一つ固定する．また， I を(0)でないK[x]のイデアルであるとし，Gを<に関するI のグレブナー基底である とする．このとき，G ∩ B≥pはI∩ B≥pの<に関するグレブナー基底である． 負でない整数を成分とするd× n配置行列A = (a1, a2, . . . , an)と，多項式環K[x]に 新たな変数t1, t2, . . . , td を加えた多項式環K[x, t]を考える．このとき， JA =⟨x1− ta1, x2− ta2, . . . , xn− tan⟩ はK[x, t]のイデアルである．この表記の下，Lemma 1.20を利用して，配置行列Aから トーリックイデアルを計算する方法を紹介する． Lemma 1.21 ([10], 補題1.5.11). 負の成分を持たないd× n配置行列Aのトーリック イデアルIAに対して，次が成り立つ． IA = JA∩ K[x]15
第
2
章
凸多面体とその三角形分割
この章では，文献[10]の第 5章に基づき，凸多面体やその三角形分割について紹介す る．最初に，2.1節で凸多面体の定義と関連する語句などの定義を行い，2.2節で凸多面体 の三角形分割の定義を行う．そして，2.3節ではイニシャル複体の定義を行う．イニシャ ル複体は正則三角形分割であることや，トーリックイデアルと三角形分割の関係を紹介す る．正則三角形分割が単模であるための必要十分条件に付いても言及する．最後に，2.4 節では凸多面体の内部に含まれる格子点の数と関わりの深いEhrhart多項式と，Hilbert 級数との関わりがある h∗ 多項式の関係について紹介する．単模な三角形分割を持つと き，h∗ 多項式がh多項式で表現できること，トーリックイデアルがスクエアフリーなイ ニシャルイデアルを持つとき，標準単項式の数を直接数えることによりh∗ 多項式を計算 できることなどを紹介する．2.1
凸多面体
集合{α1, α2, . . . , αm} ⊂ Qd に対し， conv(α1, α2, . . . , αm) = { m ∑ i=1 riαi 0≤ ri ∈ Q, m ∑ i=1 ri = 1 } とする．有限集合P に対し，P = conv(α1, α2, . . . , αm)となるような{α1, α2, . . . , αm} が存在するとき，P を凸多面体という．(凸多面体は有限個の閉半空間の有界な共通部分 としても定義される．) Definition 2.1. 凸多面体P ⊂ Qd とベクトルw ∈ Qd に対し {u ∈ P | ∀v ∈ P, w · u ≥ w · v} をP の面と言い，FACEw(P)とかく．16 第2章 凸多面体とその三角形分割 面としてP の元1つのみの集合が取れるとき，その点をP の頂点といい，Qd 上の凸 多面体P の次元dimP を，P 上の点αを固定した時に{x − α | x ∈ P}が張る空間の次 元とする．また，次元がdimP − 1となるような面をP のファセットという．凸多面体 P がちょうどdimP + 1個の頂点を持つとき，P を単体と呼ぶ．単体から成る集合∆が 次の条件を満たすとき，その集合を単体的複体と言う． (i) 任意のF ∈ ∆の面F′ は∆の元である． (ii) 任意のF, F′ ∈ ∆の共通部分F ∩ F′ はF の面でもF′ の面でもある． また，頂点が格子点であるような凸多面体P は 整凸多面体とも呼ばれる． Example 2.2. 次の凸多面体を考える．この多面体P は3次元の凸多面体であり，1次 図2.1 多面体の例P 元の面(頂点)を10個，1次元の面(辺)を15個，2次元の面を7個持つ．もちろんP 自 体もP の3次元の面である．
2.2
凸多面体の三角形分割
配置行列A = (a1, a2, . . . , an)を集合A ={a1, a2, . . . , an}とみなして考える． Definition 2.3. 単体から成る集合∆の各元の頂点が配置行列A の元の中にあるとす る．このとき， conv(A) = ∪ F∈∆ F となるならば ∆を配置行列Aの被覆と呼ぶ．さらに，配置行列A の被覆∆が単体的複 体であるならば，∆を配置行列Aの三角形分割という． 配置行列 A の被覆 ∆ の元で極大な単体 σ ∈ ∆ の頂点の集合を B とおく (B ⊂ {a1, a2, . . . , an})．d× n配置行列 Aのランクがd であるとし，Aのすべての d× dの 小行列式の最大公約数をδとおく．このとき，V (σ) = |detB|δ をσ の正規化体積という．2.3 イニシャル複体 17 全ての極大単体の正規化体積が1 であるような三角形分割∆ を，単模三角形分割とい う．次に，n次元ベクトルw = (w1, w2, . . . , wn) ∈ Qnに対し，集合∆w を次のように 定める． ∆w = { conv(ai1, ai2, . . . , air) ∃c∈ Qds.t. { aj· c = wj j ∈ {ai1, ai2, . . . , ajr} aj· c < wj j /∈ {ai1, ai2, . . . , ajr} } ベクトルw が一般の位置にあれば，∆w は配置行列Aの三角形分割となることが知られ ている．配置行列Aの三角形分割∆に対し，w ∈ Qd が存在して∆ = ∆ w となるとき， ∆を配置行列A の正則三角形分割と呼ぶ．正則三角形分割∆w は，配置行列Aをwで 1次元持ち上げたA˜に対しconv( ˜A)を考え，その下側の境界の面の集合に対応している．
2.3
イニシャル複体
配置行列A∈ Zd×n に対して，正則三角形分割を与えることができる． Definition 2.4. 配置行列 A = (a1, a2, . . . , an) ∈ Zd×nとK[x]上の単項式順序<に 対して，次の集合∆(in<(IA))をイニシャル複体という． ∆(in<(IA)) = { conv(B) B⊂ A, ∏ ai∈B xi ∈/ √ in<(IA) } Proposition 2.5 ([10], 定理5.5.6). 配置行列A ∈ Zd×n と固定された K[x]上の単項 式順序<を考える．このとき，w ∈ Qd が存在してin<(IA) = inw(IA)が成り立つなら ば∆(in<(IA)) = ∆wが成り立つ． Corollary 2.6 ([10], 系5.5.7). 配置行列A ∈ Zd×n と Qn 上のベクトル w に対し， inw(IA)の生成系が単項式より成るなら，次が成り立つ． √ in<(IA) =⟨xi1xi2. . . xir | conv(ai1, ai2, . . . , air) /∈ ∆w⟩ = ∩ σ∈∆w ⟨xi | aiはσ の頂点ではない⟩ Example 2.7. 次の配置行列Aを考える． A = (a1, a2, a3, a4, a5) = 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 この配置行列のトーリックイデアルは IA = ⟨x1x52 − x2x3x4⟩ で与えられる．ここで， x1 > x2 > x3 > x4 > x5より導かれるK[x1, x2, x3, x4, x5]上の辞書式順序<を考える18 第2章 凸多面体とその三角形分割 と，<に関するIAのイニシャルイデアルとその根基は in<(IA) =⟨x1x25⟩, √ in<(IA) =⟨x1x5⟩ となる．したがってこの順序<に関するAのイニシャル複体は ∆(in<(IA)) ={{a1}, {a2}, {a3}, {a4}, {a5},
conv(a1, a2), conv(a1, a3), conv(a1, a4), conv(a2, a3),
conv(a2, a4), conv(a3, a4), conv(a2, a5), conv(a3, a5),
conv(a4, a5), conv(a1, a2, a3), conv(a1, a2, a4), conv(a1, a3, a4),
conv(a2, a3, a4), conv(a2, a3, a5), conv(a2, a4, a5),
conv(a3, a4, a5), conv(a1, a2, a3, a4), conv(a2, a3, a4, a5)}
となる． 単模な三角形分割となる条件もイニシャル複体を考えることで与えられる． Proposition 2.8 ([10], 定理5.5.8). 配置行列A ∈ Zd×n と固定された K[x]上の単項 式順序<を考える．このとき，次の2条件は同値である． (i) 正則三角形分割∆(in<(IA))が単模である． (ii) √in<(IA) = in<(IA)である．
Example 2.9. 配置行列 AとしてExample 2.7の配置行列を考える．Example 2.7と
同じ辞書式順序を考えたとき in<(IA) ̸= √ in<(IA)なので，∆(in<(IA)) は単模ではな い．次に，x1 > x2 > x3 > x4 > x5より導かれるK[x1, x2, x3, x4, x5]上の逆辞書式順序 <′ を考えると，<′ に関するIAのイニシャルイデアルとその根基は in<′(IA) =⟨x2x3x4⟩, √ in<′(IA) =⟨x2x3x4⟩ となる．したがってこの逆辞書式順序 <′ に関するA のイニシャル複体∆(in<′(IA))は 単模となる．
2.4
Ehrhart
多項式と
h
∗多項式
多面体の理論におけるEhrhart多項式と，Hilbert級数などの関係について紹介する． Qd 上のd次元整凸多面体P = conv(a 1, a2, . . . , an)でP ∩ Zd ={a1, a2, . . . , an}とな るものを考える．このとき， AP = ( a1 · · · an 1 · · · 1 )2.4 Ehrhart多項式とh∗多項式 19 とする． Definition 2.10. 次元が d である整凸多面体 P = conv(a1, a2, . . . , an) ⊂ Qd で P ∩ Zd = {a 1, a2, . . . , an} となるものを考える．このとき，正規化 Ehrhart 多項式 i(P, m)は次の式で与えられる． i(P, m) = |mP∗ ∩ ZAP| ただし m∈ N, P∗ = conv((a1 1 ) , . . . ,(an 1 ) ), mP∗ ={ma | a ∈ P∗}, ZAP =Z (a 1 1 ) +· · · + Z (a n 1 ) である． 一般的に，i(P, m)は次の条件を満たしている[6]． • i(P, m)はd次の多項式 • i(P, 0) = 1 また，格子ZAP におけるP のh∗多項式h∗(P, x)を次の式で定義する． 1 + ∞ ∑ m=1 i(P, m)xm= h ∗(P, x) (1− x)d+1 一般的にh∗ 多項式に関して次のような事実がわかっている． • h∗(P, x) =∑d i=0h∗ixi ただし各h∗i は負でない整数[21] • i(P, m) =∑d i=0h∗i (m+d−i d ) • h∗ d > 0のとき，h∗i ≥ h∗1 (1≤ i ≤ d − 1) [9] 整凸多面体 P の三角形分割 ∆ に対し，∆ の f 多項式f∆(x) = ∑d+1 i=0 fi−1x i の各係 数 fi は P の i 次元の面の数を示している．(i = 0, . . . , d, f−1 = 1) ∆ の h 多項式 h∆(x) = ∑d+1 i=0 hix i はf 多項式を用いて次のように定義される[1, P.185]． h∆(x) = d+1 ∑ i=0 fi−1xi(1− x)d+1−i 整凸多面体P のh∗ 多項式とP の三角形分割∆のh多項式について次のような関係があ ることが知られている[1, Theorem 10.3]． Proposition 2.11. 整凸多面体P が単模な三角形分割∆を持つとする．このとき，P のh∗多項式と∆のh多項式について次が成り立つ． h∗(P, x) = h∆(x)
20 第2章 凸多面体とその三角形分割 もし，配置行列AのトーリックイデアルIAに対して，K[x]上の単項式順序<が存在し
て，IAの<に関するイニシャルイデアルがスクエアフリーとなるならば，Proposition 2.8
から∆(in<(IA))が単模であることが言える．すると，単模な三角形分割が存在するの
で，Proposition 2.11から，conv(A)のh∗多項式と∆(in<(IA))のh多項式が一致する．
そして，h多項式はf 多項式を用いて表示できる．f 多項式の各係数fiは∆(in<(IA))の
i次元の面の数と一致しており，これはスクエアフリーな標準単項式の数と一致している． ゆえに，スクエアフリーな i + 1次の標準単項式の数を直接数えることによってh∗ 多項 式を決定することができる．
21
第
3
章
マルコフ基底とグレブナー基底
この章では文献[10]の第4章に基づき，統計学でよく見られる分割表を使った検定問題 などに対して有効なマルコフ基底を紹介し，グレブナー基底との関係を見る．まず，3.1 節では分割表の紹介をする．分割表で考えたいことやその検定の方法について言及する． 次に，3.2節ではマルコフ基底を定義する．このマルコフ基底は分割表の検定問題に利用 される．最後に，3.3節でマルコフ基底とトーリックイデアルの関係について紹介する． 分割表から配置行列が決まることや，マルコフ基底から作られる2項式のイデアルがトー リックイデアルと一致することを紹介する．第1章で紹介した消去定理を利用すれば，グ レブナー基底を計算できることからマルコフ基底を決定できる．3.1
分割表
平均や共分散など，統計学に関する手続きを経て得られる数値等を統計量と呼ぶ．ま た，統計量は何らかの関数の形で得られることが多く，その変数を母数と呼ぶ．統計量に 関する推定等を行う場合, 興味のある変数とそうでない変数がある．興味のない変数を局 外母数と呼ぶ． Definition 3.1. 母数がθ である確率変数X = (X1, . . . , Xr)に対し，統計量T (X)を 考える．具体的な統計量T を与えたとき，条件付き確率 p(X = x | T (X) = t) が母数θ によらないとき，T (X)を母数θの十分統計量と呼ぶ． 2つ以上の変数の間の関係を数量などで示し，表の形にまとめたものを分割表と呼ぶ． 例えば，数科目のテストの点数をまとめたものなどが該当する． Example 3.2. 表3.1 のような分割表が得られたとする．ただし，数字は架空の物で22 第3章 マルコフ基底とグレブナー基底 ある． 代数/解析 60点未満の人数 60点以上の人数 xo= 60点未満の人数 12 20 60点以上の人数 18 15 表3.1 代数と解析の点数の分布 この例は2つの科目の得点が60点以上か未満の 2つの要素から成るので，2× 2分割 表と呼ばれる．こういった分割表で調べたいことは「変数同士が関連するかどうか」であ る．上記の例でいえば，「代数学の得点と解析学の得点は関連性があるか」である．得ら れたこの表から結論として2つの変数が関連していることが言えれば良いが，この表がた またまこの結果になっただけで，本当は関係ない事象かもしれない．こういった，偶然の 結果なのかどうかは統計的仮説検定の考え方で判断する．多くの場合，この2つの変数に は関係がない，と仮定して考えていく．このような仮定は帰無仮説と呼ばれる．変数が2 つ以上だとしても同様である．ここで，Example 3.2の分割表について，帰無仮説を適用 して，「代数の点数と解析の点数は独立である」と仮定する．それぞれの当てはめ値(期待 値)は表3.2のようになる．例えば，最初のセルの当てはめ値は65× 3265 × 3065 = 14.77で 代数/解析 60点未満の人数 60点以上の人数 計 60点未満の人数 14.77 17.23 32 60点以上の人数 15.23 17.77 33 計 30 35 65 表3.2 表3.1のデータの当てはめ値 ある．この値を元に適合度カイ2乗検定統計量を計算すると χ2(xo) = (12− 14.77) 2 14.77 + (20− 17.23)2 17.23 + (18− 15.23)2 15.23 + (15− 17.77)2 17.77 = 1.90 となる．一般に,この適合度カイ2乗検定統計量は,帰無仮説の下でカイ2乗分布に漸近 的に従うことが知られている[10]．データによっては，検定統計量の漸近分布を利用する ことが適切でない場合があり，その場合，有意確率(p値)を求めたいが，標本のサイズや 分割表の都合などにより直接計算することが困難な場合がある．その場合に取られるのが モンテカルロ法であり，特にマルコフ連鎖を用いたモンテカルロ法が強力であることが知 られている．
3.2 マルコフ基底 23
3.2
マルコフ基底
分割表に現れる数値の列をxとおく．局外母数に関する十分統計量tを行列Aを用い てt = Axと表し，固定しておく．ここで，行列Aは配置行列であると仮定する．固定 した十分統計量tが具体的に与えられたとき，その統計量が等しいものをt-ファイバーと 呼び， Ft ={x ≥ 0 | Ax = t} と書く．このとき，有意確率(p値)は次の式で定義される． p = ∑ x∈Ft χ2(x)≥χ2(xo) h(x) ただし，h(x)は指定された分布と帰無仮説のもと，xが生じる確率である．ここで，d× k配置行列Aの核KerZ(A)を考えると，KerZ(A) = {z ∈ Zk | Az = 0}だったので，十分
統計量が0となる整数ベクトルの集合となる．簡単にM(A) = KerZ(A)と書き，M(A) の各元をmoveと呼ぶ．また，Ftの元x, y がB ⊂ M(A)によって相互到達可能である とは， y = x + N ∑ j=1 εjzj, x + n ∑ j=1 εjzj ∈ Ft, n = 1, . . . , N が成り立つようなN > 0, zj ∈ B, εj ∈ {−1, 1}, j = 1, . . . , N が存在するときに言う．相 互到達可能性はFt の同値関係となることがわかっている．この同値類をFt のB-同値 類と呼ぶ．
Definition 3.3. moveの有限集合B ⊂ M(A)がAのマルコフ基底であるとは，任意の
tに対してFt自身がB-同値類となるときに言う． このマルコフ基底を使って有意確率を計算するアルゴリズムを作ることができる[10]． このアルゴリズムではランダムウォークの考え方を採用しているが, その際,「どの状態に どの確率で移るのか」をそれぞれ決定しなければならない．ここで用いられるのがマルコ フ連鎖であり,そのマルコフ連鎖を構築するためにMetropolice-Hastings法というアルゴ リズムも利用している．アルゴリズムは次のようになっている． 入力：観測値xo，マルコフ基底B，総ステップ数N，配置行列A，帰無分布f (x)，検定 統計量T (x) 出力：有意確率(p値)の推定値
24 第3章 マルコフ基底とグレブナー基底 (2) ランダムにz∈ Bを選び，ε ∈ {−1, 1}を等確率で選ぶ． (3) x + εz ∈ Ft であれば，uを0と1の間の一様乱数であるとし，そうでなければ xnext = xとして，(5)へ移る． (4) u≤ f (x + εz) f (x) であれば，xnext = x + εzとする．そうでなければ，xnext = xと する．
(5) T (xnext)≥obsであればsig = sig + 1とする．
(6) x = xnext, count = count + 1とする．
(7) count < N であれば(2)へ移る． (8) 有意確率(p値)の推定値として sig N を出力する． この方法では,初期のステップにおいては最初に選んだ点 xo の影響を大きく受けている ことが多い．したがって, 最初の数百ステップについては棄却し,それ以降についてアル ゴリズムを適用していく．
3.3
マルコフ基底とトーリックイデアル
分割表の各数値を単項式に対応させることを考える．例えば，次のような分割表T が 得られたとする． T = 6 5 4 2 1 3 8 9 7 このとき，T を単項式u61u25u43u24u5u36u87u98u79 と対応させる．配置行列Aのmoveについ て同様のことを考えると，moveの要素には負の整数が含まれている場合がある．そこで， move の正の要素と負の要素に分けて差の形で多項式として書くことにする．すなわち， moveをm = (m1, . . . , mk)としたとき， fm= ∏ mi>0 umi i − ∏ mj<0 u−mj j と定めるということである．例えば，mが表3.3のような moveであるとする．このと 1 −2 1 m = 0 1 −1 −1 1 0 表3.3 moveの例3.3 マルコフ基底とトーリックイデアル 25 き，fm = u1u3u5u8− u22u6u7 と対応する．この対応自体はmoveでなくとも考えること ができるが，配置行列Aのmove全体に対してこの対応を考え，それらの多項式で生成さ れるイデアルを考えると，これは配置行列A のトーリックイデアルと一致している．配 置行列AのmoveがAのトーリックイデアルの元と対応するが，このmoveがマルコフ 基底と対応することが次の命題により知られている．
Proposition 3.4 ([5], Theorem 3.1). 配置行列A のmove の集合M(A)の部分集合
B = {z1, . . . , zr}がAに対するマルコフ基底であることと，{fz1, . . . , fzr}がIA の生成
系であることは同値である．
この命題によって，IAの生成系を計算できればマルコフ基底も計算できることになる．
第1章で紹介した消去定理を使えば，IAの生成系としてグレブナー基底を計算できるの
27
第
4
章
カットイデアル
この章では，グラフに付随するカットイデアルを定義し，カットイデアルの様々な結果 について紹介する．まず，4.1節では，グラフの定義と，のちに登場するグラフの用語に ついて図を交えながら準備する．次の4.2節では，グラフの頂点の分割より導かれる代数 系であるカットイデアルを定義し，同様に定義される凸多面体であるカット多面体につい ても紹介する．そして，4.3節ではカットイデアルやカット多面体の既存の結果について 紹介する．具体的には，カットイデアルの生成系についての定理や2次グレブナー基底に 関する定理，カット多面体が正規であることの予想などを紹介する．最後に，4.4節では， カットイデアルとbinary graph modelという統計モデルのトーリックイデアルと対応す ることを紹介する．この結果によりカットイデアルが統計学に有用であることが示唆され た[25]．4.1
グラフにまつわる諸定義
カットイデアルは様々なグラフより導かれるが，その定義の前にグラフの言葉を準備す る．空でない集合Aのl 個の元から成る部分集合族を[A]lと表す． Definition 4.1. 集合の組G = (V, E)がE ⊂ [V ]2 を満たすとき，Gをグラフであると 言う．また，V を頂点集合と言い，E を辺集合と言う． 頂点集合V の元を頂点と言い，辺集合E の元を辺と言う．とくに E の元はV の元 2 個から成る集合であることに注意する．頂点の数|V |が有限であるとき，グラフGは有限 グラフであると言い，任意の2つの頂点に対し，一方の頂点から辺をたどってもう一方の 頂点に到達できるときGを連結グラフと言う．グラフGが重複する辺やほかのどの頂点 も経由せず自分に戻ってくる辺であるループを持たないとき，グラフGを単純グラフと 言う．単純グラフGがm個の頂点を持つとき，Gは最大で m2−m 2 本の辺を持つ．単純28 第4章 カットイデアル グラフGがm個の頂点を持ち，m2−m 2 本の辺を持つとき，Gを完全グラフと言い，Km で表す．また，辺ei が頂点j, kをつなぐ辺である場合，それを明示してei ={j, k}とも 書く．以下，グラフGは単純グラフであるとし，V ={1, 2, . . . , n}, E = {e1, e2, . . . , er} とする． Definition 4.2. グラフ G の辺集合を E = {{i1, i2}, {i3, i4}, . . . , {i2m−1, i2m}} とす る．このとき，グラフGが長さmのサイクルであるとは，次の条件を満たすときに言う． 1. m≥ 3 2. i2j = i2j+1 (1≤ j ≤ m − 1) 3. i2k ̸= i2l (k, l ∈ N, 1 ≤ k < l ≤ m) 4. i1 = i2m 長さmのサイクルをCmで表す． グラフGが連結でありサイクルを持たない場合，Gは木と呼ばれる． Definition 4.3. グラフGの頂点集合V に対し，V1∪ V2 = V かつV1∩ V2 =∅となる V1, V2 ⊂ V を考える．このとき，同じ頂点集合に属する頂点どうしの間には辺がなく，互 いに異なる頂点集合に属するいくつかの頂点どうしの間には辺があるときGを二部グラ フといい，異なる集合に属する頂点どうしには必ず辺があるとき完全二部グラフと言う． Gが完全二部グラフであるとき，|V1| = m, |V2| = nであるならばGをKm,nと書く． Definition 4.4. 頂点集合V = {1, 2, . . . , n} と辺集合E = {e1, e2, . . . , er} を持つグ ラフ G に対し，V に新たに頂点 n + 1 を加えた集合 V′ と，E に新たな辺 er+1 = {1, n + 1}, er+2 = {2, n + 1}, . . . , er+n = {n, n + 1}を加えた集合E′ を持つグラフGb をGのサスペンションと言う．図4.1のグラフは長さ4のサイクルのサスペンションで ある． 図4.1 サスペンションの例 Definition 4.5. グラフGがn個の頂点を持ち，r本の辺を持つとする．次の操作をマ
4.1 グラフにまつわる諸定義 29 イナー操作と言う． • 頂点を一つ選び，その頂点自身とその頂点につながっていた辺を除去する． • 辺を一つ選び，その辺を除去する． • 辺を一つ選び，その辺を縮約する． 辺の縮約とは，ある辺を縮めていって，その辺がつなげている頂点どうしを重ね合わせ 完全に同一視する操作である．グラフGに，上記のマイナー操作を繰り返したり組み合 わせたりして得られた新たなグラフH をGのマイナーと呼ぶ．グラフG の頂点をいく つか抜き出し，その抜き出した頂点をつなげていた辺もいくつか抜き出したグラフを部分 グラフと言い，抜き出した頂点をつなげていた辺をすべて抜き出したグラフを誘導部分グ ラフと言う．グラフG が誘導部分グラフとして長さ4以上のサイクルを持たないとき， Gはコーダルであると言う．また，連結グラフGのある辺を1本取り除いたとき，互い に連結でない2つの連結なグラフに分けてしまうなら，その辺を橋と呼ぶ．グラフGが マイナーとして完全グラフK5と完全二部グラフK3,3のどちらも持たないとき，Gを平 面グラフと言う．K5やK3,3は平面に描いたとき，必ず交差する辺がある．逆に，辺を交 差させずに平面に描けるグラフはK5とK3,3のどちらもマイナーに持たないことからこ のように呼ばれる．また，グラフGが誘導部分グラフとしてm頂点の完全グラフを持つ とき，その完全グラフを大きさmのクリークとも言う． グラフG1はコーダルグラフの G1 G2 G3 G4 G5 図4.2 コーダル・部分グラフ・誘導部分グラフ・橋・クリークの例
30 第4章 カットイデアル 例であり，G2はG1の部分グラフ，G3 はG1の誘導部分グラフである．グラフG4の黒 く塗られた頂点の間の辺は橋であり，グラフG5は大きさ4のクリークを持っている． Definition 4.6. グラフG, H の頂点集合をV1, V2とし，辺集合をE1, E2 とする． また，G, H それぞれの頂点集合の共通部分V1∩ V2，辺集合の共通部分E1∩ E2 を持つ グラフ(V1∩ V2, E1∩ E2)が大きさlのクリークであるとする．このとき，新たな頂点集 合V1∪ V2 とE1 ∪ E2 を持つグラフG′ を考える．このグラフG′ をGとH のクリーク サムと言う[25]． 共通部分として大きさ lのクリークのみを持つグラフどうしのクリー クサムはl− 1サムとも呼ばれる．次のグラフG6, G7 はそれぞれ大きさ3のクリークを 一つ持つ．そのクリークでのG6とG7 のクリークサムがG8 である． G6 G7 G8 図4.3 2サムの例
4.2
カットイデアル
グラフGが連結であり，頂点集合V ={1, 2, . . . , m}と辺集合E ={e1, e2, . . . , er}を 持つとする．ここで，次のようなA, B ⊂ V について考える． A∩ B = ∅, A ∪ B = V この条件を満たすA, B をV の分割と言い，A|B と表す．あるV の分割A|Bに対して δA|B = (d1, d2, . . . , dr)∈ {0, 1}r の各成分を次のように定める． di = { 1 |A ∩ ei| = 1 (ei ={j, k}) 0 それ以外 このとき，次の配置行列を考える． AG = δA1|B1 δA2|B2 · · · δAN|BN 1 1 · · · 1 4.2 カットイデアル 31 ただし，{δA|B | A, B ⊂ V, A ∩ B = ∅, A ∪ B = V } = {δA 1|B1, δA2|B2, . . . , δAN|BN}か つN = 2m−1 である．この配置行列AGのトーリックイデアルIA をグラフGのカット イデアルと言い，IGで表す．次に，多項式環K[q]を K[q] = K[qA1|B1, . . . , qAN|BN] で定める．ただし，Ai∩ Bi =∅, Ai∪ Bi = V (G), 1≤ i ≤ N である．カットイデアルの 配置行列の各列は上記の条件を満たすAi，Biの取り方によって一意的に定まるので，カッ トイデアルの各変数とAi|Biが1対1で対応する．qAi|Bi はグラフGの頂点集合V の分 割Ai|Bi に対応する変数ということである．また，Cut(G) = conv(δA1|B1, . . . , δAN|BN) をカット多面体と言う．カット多面体は整凸多面体である．カット多面体Cut(G)が正 規であるとは， Z≥0AG =ZAG∩ Q≥0AG が成り立つときに言う．この定義は代数的な正規の定義と対応しており，K[x]/IG が整 閉であることと同値であることがわかっている． Example 4.7. グラフGを長さ4のサイクルであるとする． 1 2 3 4 e1 e2 e3 e4 この場合，V = {1, 2, 3, 4}, E = {e1 = {1, 2}, e2 = {2, 3}, e3 = {3, 4}, e4 = {1, 4}} である．V の分割 A|B = {1, 2}|{3, 4} に対し，δA|B = (d1, d2, d3, d4) を計算する． |A ∩ e1| = 2であるから，d1 = 0である．同様に計算するとd2 = 1, d3 = 0, d4 = 1と なり，δA|B = (0, 1, 0, 1)となる．すべてのV の分割についてこのように計算することに よって，配置行列 AG = 0 1 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 を得る．カットイデアルは ⟨x2x7− x1x8, x3x6− x1x8, x4x5− x1x8⟩ となる．
