關(guān)于卡方復(fù)形的強shellable性質(zhì)

鄭 露，郭 錦

（海南大學(xué)理學(xué)院，海南 ?？?570228）

單純復(fù)形，簡稱為復(fù)形，是一種應(yīng)用廣泛的數(shù)學(xué)結(jié)構(gòu).在Stanley-Reisner對應(yīng)之下，可以通過探討單純復(fù)形的頂點可分解、shellable等性質(zhì)，研究其對應(yīng)的單項式理想的（序列）Cohen-Macaulay等性質(zhì)［1-4］.文獻［5］給出了一類由復(fù)形Δ的一個染色χ出發(fā)構(gòu)造的復(fù)形Δχ（卡方復(fù)形），并證明了這些復(fù)形Δχ都是純復(fù)形且頂點可分解，因而是shellable純復(fù)形，進而都是Cohen-Macaulay復(fù)形.

Guo等［6-7］定義并研究了一類特殊的shellable復(fù)形，稱為強shellable復(fù)形.其優(yōu)于一般shellable復(fù)形之處在于強shellable純復(fù)形的極大面理想都具有線性商.

單純復(fù)形與圖論有著非常緊密的聯(lián)系.對于一個有限簡單圖，可以定義其獨立復(fù)形，該復(fù)形以圖的頂點集作為基礎(chǔ)集，以圖的獨立點集作為面.若圖的獨立復(fù)形具有某些特定性質(zhì)，就稱該圖具有對應(yīng)的性質(zhì).關(guān)于圖的某類性質(zhì)的研究也是組合交換代數(shù)的一個重要課題［8-11］.文獻［12］中構(gòu)造了各種“whiskered”圖類，具有較好的組合代數(shù)性質(zhì)，如頂點可分解、shellable、強shellable等.為探討卡方復(fù)形的強shellable性質(zhì)，筆者定義一類TA復(fù)形后驗證了其上任一染色所對應(yīng)的卡方復(fù)形Δχ都具有強shellable性質(zhì)，并證明了復(fù)形Δ在任意一個染色χ下的卡方復(fù)形Δχ都是matroid，當(dāng)且僅當(dāng)Δ是單形.此外，還分析了“whiskered”圖在復(fù)形層面上所對應(yīng)的卡方復(fù)形是否具有類似的性質(zhì).

1 預(yù)備知識與卡方復(fù)形

對于頂點集V={x1，x2，…，x n}，定義在V上的一個復(fù)形Δ是V的一個子集族，滿足：對任意F∈Δ以及G?F，都有G∈Δ.復(fù)形Δ里的元素叫作面，所有面中按照集合包含關(guān)系的極大者稱為極大面，所有極大面構(gòu)成的集合記作F(Δ).面F的維數(shù)定義為dim(F)=|F|-1，而復(fù)形Δ的維數(shù)定義為dim(Δ)=max{dim(F)|F∈Δ}.若Δ所有的極大面都具有相同的維數(shù)，則稱Δ為純復(fù)形.若Δ只有一個極大面，則稱Δ為單形.

定義1 設(shè)Δ為一個復(fù)形，如果存在Δ的極大面集F(Δ)上一個全序F1，F(xiàn)2，…，F(xiàn) n，滿足以下條件，則稱復(fù)形Δ具有強shellable性質(zhì)，而稱該全序F1，F(xiàn)2，…，F(xiàn) n為一個強shelling序：

對任意的1≤i＜j≤n，存在1≤k＜j，使得以下3個條件同時成立：

1）|F jF k|=1；

2）F jF k?F jF i；

3）F kF j?F i.

定義2 設(shè)Δ為一個復(fù)形.若極大面集F(Δ)滿足以下調(diào)換條件，則稱Δ為一個matroid復(fù)形：對任意的A，B∈F(Δ)，以及任意的a∈AB，都存在b∈BA，使得(A{a})∪∈F(Δ)成立.

設(shè)G為一個簡單圖，V(G)為其頂點集，E(G)為其邊集.對于A?V(G)，若不存在x，y∈A，使得{x，y}∈E(G)成立，則A叫作圖G的一個獨立點集.圖G所有獨立點集組成的集合記為Ind(G).顯然，對任意獨立點集A，若B?A，則B仍然是一個獨立點集.故Ind(G)也是一個復(fù)形，稱為圖G的獨立復(fù)形，其極大面為圖G的極大獨立點集.若獨立復(fù)形Ind(G)具有強shellable性質(zhì)，則稱圖G為強shellable圖.

在文獻［5］中引入了平衡復(fù)形的定義.本文的主要研究對象卡方復(fù)形就是一類平衡復(fù)形.

實際上，要求每一個面F i滿足|F i∩F j|≤1，等價于要求每一個極大面F i滿足|F i∩F j|≤1.

在文獻［5］中給出了一類平衡復(fù)形的構(gòu)造方法，對任意一個復(fù)形Δ及Δ上的任意一個染色χ，基于Δ的面可構(gòu)造一些新的基數(shù)相等的集合，以這些集合作為極大面生成的復(fù)形，記為Δχ.為了表述的方便，稱這類復(fù)形為卡方復(fù)形（χ-complex）.確切的定義如下.

由構(gòu)造1可知，卡方復(fù)形是純的.易見，由一個s-染色所構(gòu)造的卡方復(fù)形的維數(shù)為s-1.并且，該卡方復(fù)形是s-可染的，故為一個平衡復(fù)形，如例1所示.

例1 設(shè)Δ=x1x3，x2x3x4，χ：{x1，x4}∪{x2}∪{x3}為Δ的一個染色.那么集合Δ為如下集合：{?，x3，x2，x2x3，x1，x1x3，x4，x4x3，x4x2，x4x2x3}.根據(jù)定義，Δχ的極大面集為F(Δχ)={y1y2y3，y1y2x3，y1x2y3，y1x2x3，x1y2y3，x1y2x3，x4y2y3，x4y2x3，x4x2y3，x4x2x3}.

定理1（文獻［5］定理7）設(shè)Δ是一個復(fù)形，χ是Δ的一個s-染色，那么Δχ是頂點可分解的.

由定理1可知，對任意一個復(fù)形以及其上任意一個s-染色，Δχ總是頂點可分解的，而復(fù)形的頂點可分解性質(zhì)與強shellable性質(zhì)一般情況下不能互相推導(dǎo)［6］.因此，對卡方復(fù)形的強shellable性質(zhì)的研究也有著非常重要的意義.

定理2（文獻［5］推論9） 設(shè)Δ是一個復(fù)形，χ是Δ的一個s-染色，那么Δχ一個是shellable復(fù)形，且若F1，F(xiàn)2，…，F(xiàn) m是Δ所有面的一個升維排列序列，那么F1∪τ1，F(xiàn)2∪τ2，…，F(xiàn) m∪τm是Δχ的一個shelling序列.

由定理1可知，Δχ是一個shellable復(fù)形.定理2的后半部分則給出了Δχ的一個shelling序列的構(gòu)造方法.受此啟發(fā)，用類似的方法尋找Δχ的一個強shelling序列.

2 卡方復(fù)形的強shellable性與matroid性

主要研究卡方復(fù)形的強shellable性質(zhì).研究強shellable性質(zhì)，需要構(gòu)造強shelling序，因此定義了卡方復(fù)形極大面上的一個全序關(guān)系.

其中，

顯然σ是一個單射.

易見，?χ為定義在Δχ所有極大面上的一個全序關(guān)系.例1中給出了一個卡方復(fù)形Δχ所有極大面的集合，其書寫順序就是按照?χ的一個排序.

可以證明以下結(jié)論.

定理3 設(shè)Δ是定義在V={x1，x2，…，x n}上的一個復(fù)形.令染色χ：V={x1}∪{x2}∪…∪{x n}，那么Δ在染色χ下的卡方復(fù)形Δχ是一個強shellable復(fù)形.

證明設(shè)Δ={F1，F(xiàn)2，…，F(xiàn) m}，那么由構(gòu)造1可知Δχ是V∪{y1，y2，…，y n}上的一個復(fù)形.下面證明該卡方復(fù)形極大面上的字典序是Δχ的一個強shelling序列.

對任意的1≤i＜j≤m，不妨設(shè)σ(F i∪τi)=(i1，i2，…，i n)，σ(F j∪τj)=(j1，j2，…，j n)，其中i r，j r∈{0，r}，r∈[n].由于F i∪τi?χF j∪τj，那么由定義4可知存在r∈[n]，使得i1=j1，…，i r-1=j r-1，i r＜j r，所以有x r∈F jF i和y r∈τiτj.令F k=F j{x r}，易見F k∈Δ，則在F(Δχ)中有一個極大面為F k∪τk.直接驗證可知，τk=τj∪{y r}.易見，F(xiàn) k∪τk?χF j∪τj，且有

以及

由此可見，Δχ的極大面上的字典序是一個強shelling序列.因此，Δχ是一個強shellable復(fù)形.

在文獻［9］中構(gòu)造了一系列的“whiskered”圖，從圖的角度得到了以下結(jié)論，而通過定理3可以得到如下的一個結(jié)論.

推論1（文獻［9］推論5.3）設(shè)G為一個簡單圖，其中頂點集V(G)={x1，x2，…，x n}，邊集為E(G).在圖G的基礎(chǔ)上構(gòu)造一個新的圖G W，使得其頂點集為V(G)∪{y1，y2，…，y n}，邊集為E(G)∪{{x1，y1}，{x2，y2}，…，{x n，y n}}.那么G W是一個強shellable圖.

證明設(shè)Δ=Ind(G)，令χ：V={x1}∪{x2}∪…∪{x n}為Δ的一個染色.顯然Ind(G W)=Δχ，那么由定理3可知Ind(G W)是一個強shellable復(fù)形，因此G W是一個強shellable圖.

對于任意一個簡單圖，總會存在唯一一個獨立復(fù)形與之對應(yīng)，但并不是所有復(fù)形都能作為某個圖的獨立復(fù)形.故在復(fù)形上考慮的問題更具有一般性.

定理3說明對任意一個復(fù)形Δ，總會存在一個染色χ（即基礎(chǔ)集上每個點染不同色），使得對應(yīng)的卡方復(fù)形是一個強shellable復(fù)形.類似地，對于一個復(fù)形Δ，若Δ在任意一種染色下的卡方復(fù)形都為強shellable復(fù)形，則Δ應(yīng)當(dāng)滿足某種條件.為了探究此條件，先引入以下概念.

設(shè)Δ為定義在基礎(chǔ)集V上的一個復(fù)形，φ是V上的一個置換.定義映射

定義5 設(shè)Δ為定義在基礎(chǔ)集V上的一個復(fù)形.若對任意不共面的2點x，y∈V（即{x，y}?Δ），由x，y的對換φ，

所誘導(dǎo)的映射φˉ都是Δ的自同構(gòu)，則稱Δ為一個TA復(fù)形.

定理4 設(shè)Δ為一個TA復(fù)形，那么對于Δ的任意一個染色χ，Δχ是一個強shellable復(fù)形.

對任意的1≤i＜j≤m，不妨設(shè)σ(F i∪τi)=(i1，i2，…，i s)，σ(F j∪τj)=(j1，j2，…，j s)，其中i1，i2，…，i s∈{0，1，…，n}，j1，j2，…，j s∈{0，1，…，n}.由于F i∪τi?χF j∪τj，那么由定義4可知存在r∈[s]，使得i1=j1，…，i r-1=j r-1，i r＜j r.

若i r=0，則F i∩V r=?，所以y r∈τiτj，且存在x j r∈V r，使得x j r∈F jF i.令F k=F j{x j r}，易見F k∈Δ，則在F(Δχ)中有一個極大面為F k∪τk.直接驗證可知τk=τj∪{y r}.易見，F(xiàn) k∪τk?χF j∪τj，且

和

則在F(Δχ)中有一個極大面為F k∪τk.直接驗證可知τk=τj.由于

因此，F(xiàn) k∪τk?χF j∪τj，且

和

由此可見，Δχ的極大面集上的字典序是Δχ的一個強shelling序列.因此，Δχ是一個強shellable復(fù)形.

則對該復(fù)形Δ的任意一個s-染色χ，Δχ是一個強shellable復(fù)形.

證明易見這里所構(gòu)造的復(fù)形Δ是一個TA復(fù)形，所以由定理4可知結(jié)論成立.

此外，直接檢驗可知，推論4中所構(gòu)造的復(fù)形Δ是一個matroid復(fù)形，但在某些染色下對應(yīng)的卡方復(fù)形Δχ并不是matroid復(fù)形.因此，考慮了一個復(fù)形應(yīng)當(dāng)具備怎樣的性質(zhì)，才能使得該復(fù)形在任意染色下對應(yīng)的卡方復(fù)形總是matroid復(fù)形，且得出了如下結(jié)論.

命題1 設(shè)Δ是一個復(fù)形.那么，對于Δ的任意一個染色χ，Δχ是matroid的當(dāng)且僅當(dāng)Δ是一個單形.

證明設(shè)V={x1，x2，…，x n}為Δ的基礎(chǔ)集.若Δ為一個單形，那么Δ= {x1，x2，…，x n}.顯然，Δ只有一個染色，即V={x1}∪{x2}∪…∪{x n}，記為χ.令Δ={F1，F(xiàn)2，…，F(xiàn) m}，證明Δχ的極大面集上的字典序是Δχ的一個強shelling序列.

對任意的i，j∈[m]，i≠j，有a∈(F i∪τi)(F j∪τj)，此時有2種情形.

情形1a∈F iF j，不妨設(shè)a=x t，那么y t∈τjτi.取F k=F i{x t}，顯然F k∈Δ，那么Δχ有一個極大面為F k∪τk，且τk=τi∪{y t}.進而有y t∈(F j∪τj)(F i∪τi)和

情形2a∈τiτj，不妨設(shè)a=y s，那么x s∈F jF i，進而有x s∈(F j∪τj)(F i∪τi).此時考慮F k=F i∪{x s}?V，由于Δ是一個單形，所以F k∈Δ.由此可知Δχ有一個極大面為F k∪τk，且τk=τi{y s}.于是

綜上所述，Δχ是一個matroid復(fù)形.

反之，若對于Δ的任意一個染色χ，Δχ是matroid的.用反證法.假設(shè)Δ不是單形，那么Δ至少會存在2個不同的極大面F1，F(xiàn)2.令染色χ為V={x1}∪{x2}∪…∪{x n}.那么Δχ會存在2個不同的極大面F1∪τ1，F(xiàn)2∪τ2，其中τi={y j|{x j}∩F i=?}，i=1，2.由于F1?F2，故F1F2≠?，不妨設(shè)x1∈F1F2，那么y1∈τ2τ1.考慮F2∪(τ2{y1})，對任意的r∈[n]，r≠1，總有x r∈F2或者y r∈τ2{y1}.又因為Δχ是matroid的，故必有

由Δχ的定義可知F2∪{x1}∈Δ，這與F2是極大面矛盾，故Δ是一個單形.