Semi-unmixed 二部グラフの辺イデアルについて
東平 光生
∗明治大学研究・知財戦略機構
†1 導入
K は体とし，S は体 K 上の n変数多項式環 K[X1, . . . , Xn] とする．G はグラフと し，Gの辺は Gの相異なる頂点 2つの組で表す（すなわち，本稿で扱うグラフはグラ フ理論では無向単純グラフと呼ばれるグラフに限る）．グラフ G の頂点集合をV(G)， 辺集合を E(G) とそれぞれ表す．S の各変数にグラフ G の頂点をそれぞれ対応させ，
V(G) ={1, . . . , n}と表すことにする．
I(G) は G から与えられる S の square-free な単項式イデアルであって，I(G) = (XiXj| {i, j} ∈ E(G))と定義される．I(G)はGの辺イデアル(edge ideal) と呼ばれ，
1990年に Villarreal により[11] の中で導入された．主にS/I(G) がCohen–Macaulay となるグラフGの構造について研究がなされた．2005年にHerzog–日比により，二部グ ラフH のもとで，S/I(H)のCohen–Macaulay性と順序構造の対応(本稿の系4.9を参 照) が明らかにされた．2007年にはVillarreal により二部グラフH のもとで，S/I(G) のunmixed性と擬順序構造の対応(本稿の系2.5を参照)が明らかにされた．本稿で定義 し，考察するsemi-unmixed性は安易な拡張であるが，unmixed性やCohen–Macaulay 性の必要条件に位置する．二部グラフにおける辺イデアルの結果を，少しでも拡張した形 で述べることが本稿の目的である．
本稿の構成について述べる．第2節では，Herzog–日比のCohen–Macaulay二部グラ フやVillarrealのunmixed 二部グラフの判定法に現れる条件を再考察することにより，
semi-unmixed 二部グラフの特徴づけを与える．第 3節では，semi-unmixed 二部グラ フのregularityを計算する．第 2節で求めたsemi-unmixed 二部グラフの特徴づけを応 用し，Kumminiのunmixed 二部グラフの結果を用いて，semi-unmixed 二部グラフの regularityを誘導マッチング数を用いて計算する．第4節では，semi-unmixed二部グラ フの条件とsequentially Cohen–Macaulay性の関係を考察をする．semi-unmixed二部
∗e-mail : [email protected]
†〒214-8571神奈川県川崎市多摩区東三田1-1-1
グラフのsequentially Cohen–Macaulay性の特徴づけを与え，系として Herzog–日比の
Cohen–Macaulay二部グラフの特徴づけを述べる．第5節では，ほとんど完全な多部グ
ラフのunmixed性における，semi-unmixed二部グラフの応用を述べる．
2 Semi-unmixed 性
まず，Semi-unmixed性を定義する．Gはグラフとし，V はV(G)の部分集合とする．
V がGの独立集合であるとは，V はGのいかなる辺eも含まないことをいう．∆(G)で Gの独立集合全体を表すことにし，F(G)で∆(G)の極大な元全体を表すことにする．ま た|F(G)|をグラフGの次元と呼ぶことにし，dimGと表すことにする．Gがunmixed であるとは，Gの任意の極大な独立集合V に対してdimG=|V|が成り立つことである．
定義 2.1 グラフGがsemi-unmixedであるとは，Gのある極大な独立集合Z が存在し て，Z と異なるGのすべての極大な独立集合V に対してdimG=|V|が成り立つことで ある．また，Gの極大な独立集合Z に対して，Gが上記の条件をみたすとき，GはZ に 関してsemi-unmixedであると呼ぶ．
次に，semi-unmixed性の調査を行うのに必要なグラフの記号や，辺イデアルに関する
基礎事実について述べる．
V はV(G) の部分集合とする．頂点集合をV に制限したGの誘導部分グラフを GV
で表す．すなわち GV は V(GV) = V，E(GV) = {{i, j} ∈ E(G)|i, j ∈ V} となる グラフである．G\V は誘導部分グラフ GV(G)\V を表すことにする．V の G におけ る近傍を NG(V) = {w ∈ V(G)| ∃v ∈ V;{v, w} ∈ E(G)} と定める．V = {v} とな るとき，NG(V) = NG(v) と表し，頂点v のGにおける近傍と呼ぶ．また，NG[V] = NG(V)∪V, NG[v] =NG(v)∪ {v}とおく．これらは閉近傍と呼ばれるが，本稿ではこれ らも単に近傍と呼ぶことにする．degG(v) =|NG(v)|とおき，頂点vのGの次数と呼ぶ．
degG(v) = 0のとき，vはGの孤立点と呼ばれる．Gの孤立点全体をiso(G)で表すこと にする．Gがsemi-unmixedであることと，G\iso(G)がsemi-unmixedであることは同 値である．
辺イデアルは Stanley–Reisnerイデアルであることに注意する．実際，辺イデアルは square-freeな単項式イデアルである．詳しく言えば，∆(G)はV(G)上の単体的複体と みなせ，辺イデアルI(G)は∆(G)のStanley–Reisnerイデアルに一致する．
S/I(G)の素因子イデアル全体は，その極小素イデアル全体に一致する．辺イデアル I(G)の極小素イデアル全体をMin(G)で表すことにする．単体的複体∆(G)のファセッ ト全体はF(G)である．PC = (Xi|i ∈C)とおく．Stanley–Reisner環の理論によって，
Min(G) = {PC|V(G)\C ∈ F(G)}が成り立つ．S/I(G)のクルル次元は∆(G)の単体 的複体の次元に1を加えた値に一致する．すなわちdimS/I(G) = dim ∆(G) + 1である．
記 号 の 準 備 の 最 後 に ，本 稿 の メ イ ン と な る 二 部 グ ラ フ に 用 い る 記 号 を 定 義 す る ． V1, . . . , Vc は V(G) の 部 分 集 合 と す る ．G = (G;V1, . . . , Vc) と 書 い た ら ，V(G) = V1 ⊔ · · · ⊔Vc という頂点集合の分割をもつグラフ G を表すことにする．さらにこの とき，V1, . . . , Vc がGの独立集合であるならば，G= (G;V1, . . . , Vc)は多部グラフであ ると呼ぶ．c= 2であるとき，G= (G; V1, V2)は二部グラフである．(G; V1, V2)が完全 二部グラフであるとは，任意のv1 ∈V および任意のv2 ∈V2 に対して，{v1, v2}がGの 辺であることをいう．(G;V1, . . . , Vc)が完全多部グラフであるとは，相異なる任意のi, j に対して，(GVi∪Vj; Vi, Vj)が完全二部グラフであることをいう．
本節では以下，H は孤立点のない二部グラフでH = (H; X, Y)とし，r=|X|, s =|Y| とおく．Semi-unmixed性に関する基本的な主張は以下である．
定理 2.2 Z はH の極大な独立集合とする．二部グラフ(H;X, Y)における以下の条件 は同値である．
(1) H はZ に関してsemi-unmixedである．
(2) X ̸= Z であるならば r = s である．さらに，H の頂点のある番号付け X = {x1, . . . , xr}, Y ={y1, . . . , ys}が存在して以下の条件をみたす．
(CM1) 任意のi(1≤i≤r)に対して，{xi, yi}はH の辺である．
(CM3)Z {xi, yj}と{xj, yk}がH の辺であって{xi, yk}⊈Z ならば，{xi, yk}も H の辺である．
(CP)Z 各j(1≤j ≤s)に対して次が成り立つ．{xj, yj} ∩Z =∅であるならば，
H(NH(yj)∩Z)∪(Y\Z)とH(X\Z)∪(NH(xj)∩Z)は完全二部グラフである．
(3) P が I(H) に 属 す る 極 小 素 イ デ ア ル で P ̸= PV(H)\Z な ら ば ，dimS/P = dimS/I(H)である．
(4) F が∆(H)のZ と異なるファセットであるならば，dimF = dim ∆(H)である．
(証明) (1)⇔(3)と(3)⇔(4)は定義2.1の後に紹介したStanley–Reisner環の理論に よって導かれる．
(1) ⇒ (2) : H は孤立点が存在しないから，X も Y も H の極大な独立集合であ
る．X ̸= Z である場合は，H が semi-unmixed であるから r = |X| = dimH であ る．|X| ≤ |Y| = s としているから，r = s が成り立つ．X = Z である場合も，H が semi-unmixedであるからs = |Y| = dimH である．dimH =|Y|であるから，頂点の ある番号付けX = {x1, . . . , xr}, Y = {y1, . . . , ys}が存在して(CM1) をみたす．以下，
この番号付けが(CM3)Z と(CP)Z をみたすことを示す．
(CM3)Zが成立しないとすると，Hのある辺{xi, yj}と{xj, yk}が存在して，{xi, yk}⊈ Z かつ{xi, yk} ∈/ E(H)である．{xi, yk} ⊆ F となるH の極大な独立集合F をとる．
F ̸= Z であって，H は semi-unmixed であるから dimH = |F| となる．ところが，
{xj, yj} ∩F =∅であるから，|F|<|Y|= dimH である．これは矛盾である．したがっ て，(CM3)Z が成り立つ．
1≤j ≤sを固定する．{xj, yj} ∩F =∅とする(xj が存在しないときは1点集合{yj} として考える)．xi ∈ NH(yj)∩Z, yk ∈ Y \Z とする．{xi, yk}はH の辺でないとし て矛盾を導く．(Z ∩Y)∪ {xi, yk} ⊆ F となる F ∈ F(H) をとる．yk ∈ F \Z より，
F ̸= Z である．H はZ に関してsemi-unmixedであるから，|F| = dimH である．こ こでxi ∈ F であるから，yj ∈/ F である．r+ 1 ≤ j ≤ s の場合は，xj ∈/ V(H)である から，|F| <|Y|= dimH となり矛盾である．1 ≤j ≤ rとしてよい．このときxj ∈ F である．yl ∈ NH(xj)∩Z がとれる．{xj, yl}はH の辺であるが，yl ∈ Y ∩Z ⊆ F よ り，{xj, yl} ⊆F となり矛盾である．以上により，H(NH(yj)∩Z)∪(Y\Z)は完全二部グラフ である．H(X\Z)∪(NH(xj)∩Z) が完全二部グラフであることも同様に証明できる．以上で (CP)Z が成り立つ．
(2) ⇒ (1) : F ∈ F(H)とする．F ̸= Z, |F| < |Y| とし矛盾を導く．まず，(A)「あ るj(1≤ j ≤ r)が存在して，{xj, yj} ∩F =∅となる」ことを示す．X ̸=Z の場合は，
(2)の仮定よりr = sが成り立ち，今は|F| < |Y| であるから正しい．X = Z とする．
yk ∈F がとれる．(CP)Z により，F ⊇ {yr+1, . . . , ys}が成り立つ．|F| <|Y|であった から，(A)が成り立つ．
(A)により，F のある部分集合{xi, yk}が存在して，{xi, yj}と{xj, yk}はH の辺と なる．このとき，{xi, yk} ⊈ Z の場合は(CM3)Z によって矛盾が導かれ，{xi, yk} ⊆ Z の場合は(CP)Z によって矛盾が導かれる．■
Z =X に関するsemi-unmixed二部グラフの特徴づけは以下である．
系2.3 二部グラフ(H;X, Y)における以下の条件は同値である．
(1) H はX に関してsemi-unmixedである．
(2) H の頂点のある番号付けX ={x1, . . . , xr}, Y ={y1, . . . , ys}が存在して以下の条 件をみたす．
(CM1) 任意のi(1≤i ≤r)に対して，{xi, yi}はH の辺である．
(CM3) {xi, yj}と{xj, yk}がH の辺であるならば，{xi, yk}もH の辺である．
(CP) 任意のj(r+ 1≤j ≤s)に対して，HNH(yj)∪Y は完全二部グラフである．
G は必ずしも二部グラフでないグラフとする．Semi-unmixed の定義より，G が unmixedであることと，Gの任意の極大な独立集合V に対してGがV に関してsemi- unmixedであることは同値である．この事実は二部グラフ(H;X, Y)では次のように言 い換えられる．
命題 2.4 二部グラフ(H;X, Y)における以下の条件は同値である．
(1) H はunmixedである．
(2) H の任意の極大な独立集合Z に対して，H はZ に関してsemi-unmixedである．
(3) |X|=|Y|である．さらにH はX に関してsemi-unmixedである．
系2.3と命題2.4を合わせることで，以下の主張を系として得る．
系2.5 ([12]を参照) (H;X, Y)は孤立点のない二部グラフとする．以下の条件は同値で ある．
(1) H はunmixedである．
(2) |X| = |Y| である．さらに H の頂点のある番号付け X = {x1, . . . , xr}, Y = {y1, . . . , yr}が存在して以下の条件をみたす．
(CM1) 任意のi(1≤i ≤r)に対して，{xi, yi}はH の辺である．
(CM3) {xi, yj}と{xj, yk}がH の辺であるならば，{xi, yk}もH の辺である．
3 Regularity の計算
まず regularityの定義を述べる．Gは必ずしも二部でないグラフとする．グラフGの regularityは，S/I(G)のCastelnuovo–Mumford regularityで定義される．すなわち，
reg(G) = reg(S/I(G)) = max{i+j|∗Hmi (S/I(G))j ̸={0}}
= max{j| ∃i, ToriS(K, S/I(G))i+j ̸= 0}
である．ここで，m= (X1, . . . , Xn)である．後半の等式はEisenbud–後藤の結果である．
より一般的な定義なども含めて，[1]などを参照してほしい．
次に，regularityに関連するグラフの不変量，誘導マッチング数の定義を述べる．M は
E(G)の部分集合とする．M がGの誘導マッチングであるとは，|M|= 1またはM の相 異なる2元eとf に対してe∩NG[f] = ∅が成り立つことをいう．グラフGの誘導マッ チング数はGのim(G)で表し，im(G) = max{|M| |M はGの誘導マッチング}と定義 する．Katzmanは不等式im(G)≤reg(G)を[7]の中で示した．その後，その不等式がい つ等式になるかという問題が研究されている．特にKumminiは以下の主張を証明した．
定理 3.1 ([8]を参照) H は二部グラフとする．H がunmixedであるならば，reg(H) = im(H)である．
本節では上記の Kummini の計算結果を用いて，semi-unmixed となる二部グラフの regularityの計算を行う．まず，X に関してsemi-unmixedとなる場合から考察する．
補題 3.2 (H;X, Y)は二部グラフとする．H がX に関してsemi-unmixed であるなら ば，reg(H) = im(H)である．
(証明) Unmixed でない場合を考えれば十分であるから，|X| < |Y| としてよい．
X′ は V(H)∩X′ = ∅, |X′| = |Y| − |X| をみたす新たな頂点集合とする．H に対し て，V(H′) = (X ⊔X′)⊔Y, E(H′) = E(H)∪ {{x′, y}|x′ ∈ X, y ∈ Y} となる二部 グラフ H′ = (H′; X ⊔ X′, Y) を定義する．H は H′ の誘導部分グラフであるから，
reg(H) ≤ reg(H′)が成り立つ([6]などを参照)．また，作り方からim(H) = im(H′)と なる．しかもF(H′) = (F(H)\X)∪ {X⊔X′}をみたすので，H′はunmixedとなる．
よって，
im(H)≤reg(H)≤reg(H′) = im(H′) = im(H) となり，im(H) = reg(H)を得る．■
Z ̸= X に関して semi-unmixedとなる場合(補題 3.4)を考察するために，グラフの
regularity における基本的な主張を確かめる．これは，辺をもつグラフ G の補グラフ
Gが弦グラフであることと，reg(G) = 1が同値である (例えば[2, Theorem 3.4] を参 照)ことを用いる．ここで補グラフGとは，V(G) = V(G)，E(G) = {{v, w} | {v, w}∈/ E(G), v ̸=w}をみたすグラフのことである．また弦グラフとは，そのグラフの誘導部分 グラフとして長さ4以上のサイクルが存在しないことをいう．
命題 3.3 G は 必 ず し も 二 部 で な い グ ラ フ と し ，長 さ 5 の 閉 路 を も た な い と す る ． im(G) = 1であるならば，reg(G) = 1である．
(証明) reg(G)>1とすると，主張の直前に述べた事実から，補グラフGは弦グラフで ないから，長さ4以上のサイクルを誘導部分グラフC として含む．C の長さが4である と，C の補グラフは2元からなるGの誘導マッチングとなって，im(G)>1となり仮定 に反する．一方でCの長さが5以上であると，Cの補グラフに長さ5のサイクルが現れ，
それはGのサイクルでもあって仮定に反する．以上より，reg(G) = 1である．■
補題 3.4 (H;X, Y)は二部グラフ，Z はH の極大な独立集合とし，Z ̸=X とする．H がZ に関してsemi-unmixedであるならば，reg(H) = im(H)である．
(証明) H は二部グラフであるから，命題3.3より2 ≤ im(H) ≤ reg(H)としてよい．
|X| ≤ |Y|, iso(H) = ∅ とする．r = |X|, s = |Y| とおく．定理 2.2 より，H におい てr = s であって，頂点の番号付けX = {x1, . . . , xr}, Y = {y1, . . . , yr}が存在して，
(CM1)と(CM3)Z，(CP)Z をみたす．
H に対して，二部グラフ(H∗; X, Y)を
E(H∗) =E(H)∪ {{xj, yk} | ∃i; {xi, yi} ∩Z =∅, xj ∈NH(yi)∩Z, yk ∈NH(xi)∩Z} と定める．多項式 S を，変数と頂点 V(H) を同一視して S = K[v|v ∈ V(H)] とお
く．I(H∗) = I(H) + (xiyk| {xi, yk} ∈ E(H∗)\E(H)) であるから，(CP)Z によって I(H∗)∩(w|w /∈Z) =I(H)が成り立つ．
I(H∗)とI(H)の素イデアル分解の比較により，H∗ はunmixedである．さらにH∗ の作り方から，I(H∗) + (w|w /∈ Z) = P ∩Qという二つの素イデアルによる分解を得 る．よってS 上の完全列
0−→S/I(H)−→S/I(H∗)⊕S/(w|w /∈Z)−→S/P ∩Q −→0
を 得 る ．よ っ て ，局 所 コ ホ モ ロ ジ ー に よ る regularity の 定 義 か ら ，reg(H) ≤ max{reg(S/P ∩ Q) + 1, reg(S/I(H∗))} と な る ．P ∩ Q は 完 全 二 部 グ ラ フ と い く つ か の 孤 立 点 か ら な る グ ラ フ の 辺 イ デ ア ル と み な せ る か ら ，補 題 3.2 に よ っ て reg(S/P ∩Q) + 1 = 2となる．また，定理3.1によってreg(S/I(H∗)) = im(H∗)であ る．したがって，reg(H) ≤ im(H∗)としてよい．H∗ の作り方から，im(H∗) ≤ im(H) は常に成り立つ．以上により，reg(H) = im(H)である．■
補題3.2と補題3.4を合わせれば以下の定理を得る．
定理 3.5 H は二部グラフとする．H がsemi-unmixedであるならば，reg(H) = im(H) である．
4 Sequentially Cohen–Macaulay 性
Cohen–Macaulay性が順序構造と対応し，unmixed性は擬順序構造と対応することを 背景に，semi-unmixedとなる二部グラフから抽出した条件を元に，sequentially Cohen–
Macaulay性がどのような構造と対応するかを調査し，結論(定理4.8)を述べる．本節の 主張(命題 4.4以降)の証明は，ほとんど全て組合せ論的な操作に終始する．そのため主 張の紹介に主眼を置き，証明は行わないか概略程度にとどめる．
S = K[X1, . . . , Xn]は体K 上の多項式環とし，体K は常に固定する．Sequentially Cohen–Macaulayの概念はStanleyによって以下のように定義された．
定義 4.1 ([9]) M はZ-次数付きS-加群とする．M がsequentially Cohen–Macaulayで あるとは，M の次数付き部分加群Miの列
{0}=M0 ⊆M1 ⊆ · · · ⊆Mr =M
が存在して，以下の条件をみたすことをいう．
(1) 各i(1≤i ≤r)に対して，Mi/Mi−1 はCohen–Macaulayである，
(2) dim(M1/M0)<dim(M2/M1)<· · ·<dim(Mr/Mr−1)が成り立つ．
Gはグラフとする．剰余環S/I(G)がsequentially Cohen–Macaulay となるとき，Gは
sequentially Cohen–Macaulayと呼ぶことにする．他の環の性質についても，Gの性質と して呼ぶことにする．例えば，GがCohen–Macaulayグラフであるというのは，S/I(G) がCohen–Macaulay環となることである．
命題 4.2 (H; X, Y)は孤立点のない二部グラフとする．このとき，以下の条件は同値で ある．
1. HはCohen–Macaulayである．
2. |X| =|Y|であって，H はsemi-unmixed かつsequentially Cohen–Macaulayで ある．
(証明) 定義4.1により，S/I(H)がCohen–Macaulayであることと，S/I(H)が加群の 列{0} ⊆ M1 =S/I(H)によってsequentially Cohen–Macaulayであることが同値であ る．したがって，S/I(H)の任意の極小素イデアルP に対してdimS/P = dimS/I(H) が成り立つ．定理 2.2と命題 2.4により，|X| = |Y| であって H はsemi-unmixed で ある．■
グラフの頂点の番号付けに関する性質について述べておく．条件 (P) が番号付け V(G)\iso(G) ={v1, . . . , vt}に関する性質であるとき，条件(P)を番号条件と呼ぶこと にする．(P1), . . . ,(Pl) は番号条件とする．Gが番号条件(P1), . . . ,(Pl)をみたすとは，
ある番号付けV(G)\iso(G) ={v1, . . . , vt}が存在して，番号条件(P1), . . . ,(Pl)のすべて をみたすことをいう．例えば，(CM1)や(CP)は番号条件である．また，H = (H;X, Y) がXに関してsemi-unmixedであるならば，(H;X, Y)は(CM1)と(CM3)，(CP)をみ たす．
本 稿 に お け る 二 部 グ ラ フ の sequentially Cohen–Macaulay 性 の 調 査 に は ，Tuyl–
Villarrealの以下2つの結果を用いる．
補題 4.3 ([10, Lemma 3.9]を参照) (H;X, Y)は二部グラフとし，|X| ≤ |Y|，E(H)̸=∅ とする．H がsequentially Cohen–Macaulayであるならば，H に次数1の頂点y ∈ Y が存在する．
定理 4.4 ([10, Corollary 3.11]) Hは二部グラフとし，H のある頂点vとwが存在して NH(v) = {w}をみたすとする．このとき，H がsequentially Cohen–Macaulayである ことと，H\NH[v]およびH\NH[w]がsequentially Cohen–Macaulayであることは同 値である．
以下，H = (H;X, Y)は二部グラフとし，r=|X|, s =|Y|とおく．番号条件を考える 主張については，H の孤立点は存在しないと仮定してよい．
命題 4.5 (H;X, Y)は孤立点のない二部グラフとする．Z はH の極大な独立集合とし，
Hに次数1の頂点y ∈Y が存在すると仮定する．このときH が(CM1)と(CM3)Z をみ たすならば，頂点のある番号付けX ={x′1, . . . , x′r}, Y ={y′1, . . . , ys′}が存在して(CM1) と(CM3)，y′1 =yをみたす．
(証明) 番号付けX = {x1, . . . , xr}, Y = {y1, . . . , ys}は(CM1) と(CM3)Z をみたす とする．y = yα とおく．α > r である場合は，xβ ∈ NH(yα)をとる．β ≤ r である．
yβ とyα を入れ替えて新しい番号付けを考えても，degH(yα) = 1であるため(CM1) と (CM3)Z はみたされる．よって，α≤rとしてよい．
φ は{1, . . . , r}上の置換とする．各 i(1 ≤ i ≤ r) に対しては x′φ(i) = xi, yφ(i)′ = yi
と置き，各 j(r + 1 ≤ j ≤ s) に対しては yj′ = yj とおく．すると，新しい番号付 けX = {x′1, . . . , x′r}, Y = {y′1, . . . , y′s} は(CM1) と(CM3)Z をみたす．そこで，φ を φ(α) = 1となるようにとればy =yα =y1′ となる．■
補題 4.6 ZはHの極大な独立集合とする．Hの頂点の番号付けX ={x1, . . . , xr}, Y = {y1, . . . , ys}で，(CM1)と(CM3)Z，さらにZ ⊆ ∪ri=1{xi, yi}をみたすものが存在した と仮定する．このときH がsequentially Cohen–Macaulayであるならば，(H;X, Y)は (CM1)と(CM2)，(CM3)Z をみたす．
(証明の概略) 各i(1≤i ≤r)に対して番号条件
(CM2)i : {xi, yj}がHの辺であるならば，i≤j である を考える．
H はsequentially Cohen–Macaulayであるから，補題4.3により次数1の頂点y ∈Y が存在する．y =yα とおく．仮定の(CM3)Z とZ ⊆ ∪ri=1{xi, yi}によって，α≤rとな るようにα を選べる．すると命題4.5の証明により，degH(y1) = 1となるようにでき，
(H;X, Y)が(CM1)と(CM2)1，(CM3)Z，Z ⊆ ∪ri=1{xi, yi}をみたす頂点の番号付け が存在する．
H2 =H \NH[y1]とおく．上で得た番号付けの誘導から(H2; X \ {x1}, X \ {y1})は (CM1) と，(CM3)Z，Z ⊆ ∪ri=2{xi, yi} をみたす．定理 4.4より，H2 は sequentially Cohen–Macaulayであるから，同様に命題4.5の証明からdegH
2(y2) = 1になるような 番号付けが存在し，(CM2)1 をみたすようにできる．このとき，(H;X, Y)は(CM1) と (CM2)1，(CM2)2，(CM3)Zをみたす．次はH3 =H2\NH[y2]とおき，同様の操作を繰 り返すことによって，主張の結論を得ることができる．■
補題 4.7 (H;X, Y) が(CM1) と(CM2)，(CM3) をみたすならば，H はsequentially Cohen–Macaulayである．
(証明の概略) |X| = rに関する帰納法で示す．r = 1の場合は H は常に sequentially
Cohen–Macaulayである．
r > 1 とする．番号付けX = {x1, . . . , xr}, Y = {y1, . . . , ys} は(CM1) と(CM2)， (CM3) をみたすとする．H1 = H \ NH[y1], H2 = H \NH[x1] とおく．NH[y1] = {x1, y1}, iso(H1) ⊆ {yr+1, . . . , ys}であるから，H から誘導される H1 の頂点の番号付 けは(CM1)と(CM2)，(CM3)をみたす．帰納法の仮定よりH1 はsequentially Cohen–
Macaulayである．
H2 については，(CM3)によりiso(H2) ={xi|yi ∈NH(x1),2≤i≤r}の成立が鍵で ある．この事実によって，
NH(x1)∪iso(H2) ={xi, yi|yi ∈NH(x1), 2≤i≤r} ∪ {yj|yj ∈NH(x1), r < j} が成り立つ．H2 もまた H の誘導部分グラフであるから，H から誘導される番号付けに より，H2 の頂点の番号付けもまた(CM1)と(CM2)，(CM3) をみたす．帰納法の仮定 よりH2 はsequentially Cohen–Macaulayである．定理4.4により，H はsequentially Cohen–Macaulayである．■
次の主張，補題4.8の証明は概略も含め行わない．補題4.8は，補題4.7と合わせて補 題4.6の逆である．(CM3)Z の番号条件を考える際，Z = X の場合が補題4.7であり，
Z ̸= Xの場合が補題4.8である．Z ̸=X の場合もまた，定理4.4を用いて証明すること に変わりはない．しかし，補題4.7と同様な証明は行えないため，次の番号条件を補う．
(CP)XZ : 各i(1≤i≤r)に対して，HNH(yi)∩Z∪(Y\Z)は完全二部グラフである．
番号条件(CP)XZ はsemi-unmixedであるための必要条件である(定理2.2参照)．
補題 4.8 Z は H の極大な独立集合とし，|Z| < |X| とする．H の頂点の番号付け X = {x1, . . . , xr}, Y = {y1, . . . , ys} で，(CP)XZ とZ ⊆ ∪ri=1{xi, yi}をみたすものが 存在したと仮定する．このとき (H;X, Y)がその番号付けでさらに (CM1) と(CM2)， (CM3)Z をみたすならば，H はsequentially Cohen–Macaulayである．
補題4.6と補題4.7，補題4.8により以下の定理が得られる．
定理 4.9 (H;X, Y)はZ に関してsemi-unmixedであるとする．このとき，以下の条件 は同値である．
(1) H はsequentially Cohen–Macaulayである．
(2) (H;X, Y)は(CM1)と(CM2)，(CM3)Z をみたす．
(証明) (1)⇒(2) :補題4.6による．
(2)⇒(1) : (H;X, Y)は(CM1)と(CM2)，(CM3)Z をみたするとする．Z =X の場 合は，補題4.7によりH はsequentially Cohen–Macaulayである．Z ̸=Xの場合は，同 時に(CP)Z もみたすことが，定理2.2の証明(1)⇒ (2)の部分より導かれる．したがっ
て，補題4.8によりH はsequentially Cohen–Macaulayである．■ 命題4.2と定理4.9を合わせることで，以下を系として得る．
系4.10 ([4, Corollary 9.1.14]や[3]を参照) (H;X, Y)は孤立点のない二部グラフとす る．このとき，以下の条件は同値である．
(1) H はCohen–Macaulayである．
(2) |X|=|Y|であり，(H;X, Y)は(CM1)と(CM2)，(CM3)をみたす．
5 Unmixed なほとんど完全な多部グラフへの応用
semi-unmixed の性質は，実はほとんど完全な多部グラフのunmixed性の調査の際に 現れた性質である．本節では，unmixedとなるほとんど完全な多部グラフへの応用を述 べる．
定義 5.1 ([5]) cは自然数とし，G= (G;V0, V1, . . . , Vc)は(c+1)部グラフとする．Gが ほとんど完全な多部グラフであるとは，G\V0 = (G;V1, . . . , Vc)が完全c部グラフとな ることである．
(G;V0, V1, . . . , Vc) はほとんど完全な多部グラフとする．各 i(1 ≤ i ≤ c) に対して Gi :=GV0∪Vi とおくと，(Gi;V0, Vi)は二部グラフである．次の主張は紹介をするにとど め，ここでは証明は行わない．
定理 5.2 (G;V0, V1, . . . , Vc) はほとんど完全な多部グラフとする．このとき G がun- mixedであるならば，各i(1≤i≤c)に対してGiはsemi-unmixedである
定理5.1より，ほとんど完全な多部グラフGがunmixedであるならば，Gの辺全体の 構造がわかる．これにより，そのGのregulariyは誘導マッチング数で計算ができる．以 下でそれについて述べ，本稿による報告を終える．
補題 5.3 ([5, Lemma 5.2]を参照) (G;V0, V1, . . . , Vc)はほとんど完全な多部グラフとす る．このとき，以下の性質が成り立つ．
(1) reg(G) = max{reg(G1), . . . ,reg(Gc),1}である，
(2) im(G) = max{im(G1), . . . ,im(Gc),1}である，
(3) 任意のi(1≤i ≤c)に対してreg(Gi) = im(Gi)であるならば，reg(G) = im(G)が 成り立つ．
次の主張は[5]の中で証明したが，semi-unmixedの導入によって証明が幾分か簡略化 された．
定理 5.4 ([5, Theorem 1.4]を参照) Gがほとんど完全な多部グラフでunmixedである ならば，reg(G) = im(G)である．
(証明) G= (G;V0, V1, . . . , Vc)はほとんど完全な多部グラフとし，各i(1≤i≤c)に対 してGi :=GV0∪Vi とおくと，Giは二部グラフである．定理5.1より，各i(1≤i ≤c)に 対してGi はsemi-unmixedである．定理3.5より，各i(1≤i≤c)に対してreg(Gi) = im(Gi)が成り立つ．したがって補題5.2より，reg(G) = im(G)である．■
参考文献
[1] W. Bruns and J. Herzog, Cohen–Macaulay rings, revised edition, Cambridge stud- ies in advanced mathematics 39, Cambridge University Press, 1998.
[2] A. Dochtermann and A. Engstr¨om, Algebraic properties of edge ideals via combi- natorial topology, Electron. J. Combin. 16(2) (2009), #R2.
[3] J. Herzog and T. Hibi,Distributive lattices, bipartitegraphs and Alexander duality, J. Alg. Combin. 22(2005), 289–302.
[4] J. Herzog and T. Hibi, Monomial ideals, Graduate Texts in Mathematics 260, Springer-Verlag London Limited, 2011.
[5] H. Higashidaira, On the sequentially Cohen–Macaulay properties of almost com- plete multipartite graphs, Commun. Algebra 45(6) (2017), 2478–2493.
[6] S. Jacques, Betti Numbers of Graph Ideals, Ph.D. thesis, The University of Sheffield, (2004).
[7] M. Katzman, Characteristic-independence of Betti numbers of graph ideals, J.
Combin. Theory Ser. A 113 (2006), 435–454.
[8] M. Kummini,Regularity, depth and arithmetic rank of bipartite edge ideals, J. Alg.
Combin. 30 (2009), 429–445.
[9] R. P. Stanley, Combinatorics and Commutative Algebra, Second Edition., Progr.Math., vol.41, Birkh¨auser Boston, Inc.,
[10] A. Van Tuyl and R. H. Villarreal, Shellable graphs and sequentially Cohen- Macaulay bipartite graphs, J. Combin. Theory Ser. A 115 (2008), 799–814.
[11] R. H. Villarreal,Cohen-Macaulay graphs, Manuscripta Math.66(1990), 277–293.
[12] R. H. Villarreal, Unmixed bipartite graphs, Rev. Colombiana Mat. 41 (2007), 393–395.
