郭 錦，李海燕

(海南大學 信息科學技術學院, 海南 ?？?570228)

關于余一維圖的實現的探究

郭 錦，李海燕

(海南大學 信息科學技術學院, 海南 ?？?570228)

主要探討完全圖、完全二部圖等圖類的余一維圖實現問題.

單純復形； 余一維圖； 實現

1 基本概念

Cohen-Macaulay 性質(簡稱 CM 性質)一直以來都是代數學家們十分關注的代數性質之一. 自從 Stanley 建立起單純復形與 squarefree 單項式理想之間的 Stanley 對應之后, 從組合的角度通過構造純 shellable 單純復形的方法便成了得到 CM 理想的一條主要途徑, 詳見文獻[1-5]. 國內外組合代數學家對shellable性質進行了廣泛的研究, 詳見文獻[6-9].筆者在文獻 [10] 中定義了一類特殊的 shellable 復形, 稱為強 shellable 復形. 強shellable 復形有著一般 shellable 復形不具備的屬性即其極大面理想具有線性商. 文獻 [10] 對于強shellable 復形的研究過程中, 余一維圖起到了關鍵作用. 借助余一維圖,給出了強shellable 復形的刻畫.

定理1[10]純復形Δ是強shellable的當且僅當其余一維圖Γ(Δ)是協調的并且有保距序.

由此可見, 余一維圖是研究復形的shellable性質的一個行之有效的工具. 若對于某個圖Γ, 存在一個純復形Δ, 使得Γ(Δ)=Γ則稱Γ是可以通過余一維圖實現的, 簡稱可實現的.本文主要工作探討幾類特殊圖類的實現問題.

設Δ為一個單純復形,F1，F2為其2個極大面,其距離定義為disΔ(F1,F2)：=min(dim(F1,dim(F2))-dim(F1∩F2).在單純復形Δ上定義的余一維圖, 記為Γ(Δ),是以F(Δ)為頂點集的有限圖, 極大面F與G之間連邊當且僅當disΔ(F,G)=1.在單純復形Δ的余一維圖Γ(Δ)上, 若對任意2個頂點F,G,有disΔ(F,G)=disΓ(Δ)(F,G),則稱該余一維圖(相對于單純復形Δ)是協調的. 對于簡單圖Γ0, 刪去其中一個頂點v1得到的子圖記為Γ1=Γv1.若對Γ1中任意一對頂點u,v,都有disΓ1(u,v)=disΓ(u,v),則稱子圖Γ1相對于Γ保距.進一步,若在Δ的頂點集上有一個排序v1,v2,…,vt,使得對任意i=1,…,t-1,都有Γi相對于Γi-1保距,其中Γi為Γi-1在頂點集{vi+1,vi+2…,vt}上誘導的子圖, 那么稱v1,v2，…,vt為Δ的一個保距序.

2 完全圖的實現

n階完全圖記為Kn.如果一個純復形的余一維圖實現為一個完全圖,則易見該圖是協調的.容易驗證,完全圖有保距序,且任何一種排序都是該完全圖的保距序.由定理1可得如下命題.

命題1 余一維圖為完全圖的純復形是強shellable的,從而是CM的.

例1 在集合[n]上定義單純復形Δ:=〈F1,…,Fn〉,其中Fi=[n]{i},i=1,…,n.直接驗證可知,Γ(Δ)為一個n階完全圖.

引理1 設Γ(Δ)與Γ(Δc)分別為單純復形Δ與其補復形Δc的余一維圖.若F1與F2分別為Δ的2個極大面,則disΔc([n]F1,[n]F2)=disΔ(F1，F2).進一步,圖Γ(Δ)與Γ(Δc)同構.

定理2 純復形Δ的余一維圖Γ(Δ)是一個完全圖, 當且僅當Δ或其補復形Δc為一個單形與一個單點復形的并復形,即Δ=Δ(n)*Δ(0,m)或Δc=Δ(n)*Δ(0,m).

證明 若Δ=Δ(n)*Δ(0,m),直接驗證可得,Γ(Δ)=Γ(Δ(0,m))=Km.若Δc=Δ(n)*Δ(0,m),則由引理1可得,Γ(Δ)=Γ(Δc)=Km.至此,定理2的充分性得證,下面證明其必要性.

當d=|B|+1時,設Δ1為由B生成的單形,且設Δ2=〈{a1},…,{ak}〉.易見,Δ=Δ1*Δ2,即單純復形Δ為一個單形與一個單點復形的并復形.

當d=|A|-1時,易見,Δ=〈A{a1},…,A{ak}〉.因此,Δc=〈([n]A)∪{a1}〉,…,([n]A)∪{ak}.設Δ1為由[n]A生成的單形,且設Δ2=〈{a1},…,{ak}〉.易見,Δc=Δ1*Δ2,即單純復形Δc為一個單形與一個單點復形的并復形.

證畢.

3 完全二部圖的實現

若一個圖Γ的頂點集可以劃分成2個不相交的部分U和V, 使得Γ中每一條邊都連接U中一個點和V中的一個點, 這樣的圖Γ稱為一個二部圖.進一步,若U中任意一個點與V中每一個點都有邊相連,則稱此二部圖Γ為完全二部圖,記為Km,n,其中m,n分別表示2個部分所含頂點數量.若其中一個部分只含一個頂點,這樣的完全二部圖K1,n稱為星圖.

文獻 [10] 中的結論體現了復形距離與其余一維圖中距離的關系.

命題2[10]設Δ為一個純復形.對于Δ中任意2個極大面F,G，都有不等式disΔ(F,G)≤disΓ(Δ)(F,G)成立.

設Γ為一個圖, 其直徑定義為任意2個頂點間距離的最大值,記為diam(Γ).

命題3 設Δ為一個純復形, 且設Γ(Δ) 為其余一維圖.若diam(Γ(Δ))≤2,則Γ(Δ) 是協調的.

證明 對于Γ(Δ) 的任意2個頂點F,G,若disΓ(Δ)(F,G)=1,則顯然disΔ(F,G)=1=disΓ(Δ)(F,G).若disΓ(Δ)(F,G)=2,則在圖Γ(Δ) 中,F與G不相連.因此,disΔ(F,G)>1.由命題2可知,1

證畢.

由保距序的定義可知, 完全二部圖有保距序, 且只要保證2個部分各留一個點作為序列的最后2個點, 這樣的排序都是保距序. 由定理1和命題3可得命題4.

命題4 余一維圖為完全二部圖的純復形是強shellable的, 從而是CM的.

例2 在集合{a1，…，an，b1，…，bn}上定義單純復形Δ：=〈F，F1，…，Fn〉,其中F={a1，…，an},且Fi=(F{ai})∪{bi},i=1，…，n.直接驗證可知,Γ(Δ) =K1,n.

由例2可知, 任一星圖都可以通過余一維圖實現.例3說明K2,2也可通過余一維圖實現.

例3 設單純復形Δ:=〈{1,2},{2,3},{3,4},{1,4}〉.易見,Γ(Δ) =K2,2.

定理3說明完全二部圖中只有K1,n和K2,2可以通過余一維圖實現.

定理3 若純復形Δ的余一維圖Γ(Δ) 是一個完全二部圖,則Γ(Δ) 為K1,n或K2,2.

綜上所述, 無論在哪種情形下, 都得到了矛盾,說明K1,n和K2,2之外的完全二部圖都不可通過余一維圖實現.

證畢.

[1]EisenbudD.CommutativeAlgebrawithaViewTowardAlgebraicGeometry,GTM150 [M].Berlin:SpringerScience,2004.

[2]HerzogJ,HibiT.MonomialIdeals,GTM260[M].London:Springer-VerlagLondonLimited,2011.

[3]StanleyRP.CombinatoricsandCommutativeAlgebra[M].2nded.Boston:ProgressinMathematics,BirkhauserBostonInc.,1996.

[4]HerzogJ,HibiT.DistributiveLattices,BipartitegraphsandAlexanderduality[J].J.AlgebraicCombin.,2005,22:289-302.

[5]HerzogJ,HibiT,ZhengX.Cohen-Macaulaychordalgraphs[J].J.Combin.TheorySer.A,2006,113:911-916.

[6]Bj?rnerA.ShellableandCohen-Macaulaypartiallyorderedsets[J].Trans.Amer.Math.Soc,1980,260:159-183.

[7]Bj?rnerA,WachsM.Onlexicographicallyshellableposets[J].Trans.Amer.Math.Soc,1983,277:323-341.

[8]Bj?rnerA,WachsM.Shellablenonpurecomplexesandposets(Ⅰ)[J].Trans.Amer.Math.Soc,1996,348:1 299-1 327.

[9]Bj?rnerA,WachsM.Shellablenonpurecomplexesandposets(Ⅱ)[J].Trans.Amer.Math.Soc,1997,349:3 945-3 975.

[10]GuoJ，ShenYH，WuTS.Strongshellabilityofsimplicialcomplexes[EB/OL].[2016-10-20].http:∥lanl.arxiv.org/abs/1604.05412.

Realization of Codimension One Graph

Guo Jin, Li Haiyan

(College of Information Science and Technology, Hainan University, Haikou 570228, China)

In the report, the realization of codimension one graph including complete graphs and complete bipartite graphs was discussed.

simplicial complex; codimension one graph; realization

2016-11-03

國家自然科學基金(11526065, 11271250)；海南省自然科學基金(20161002, 20161003)；海南大學博士科研啟動基金(kyqd1511, kyqd1510)

郭錦(1983-), 男, 湖南湘潭人, 博士, 講師, 研究方向: 組合交換代數, E-mail: guojinecho@163.com

李海燕(1988-), 女, 山西原平人,博士，講師, 研究方向: 圖論, E-mail:lhy9694@163.com

1004-1729(2017)01-0007-04

O 153.3

A DOl：10.15886/j.cnki.hdxbzkb.2017.0002