羅士峰，鄧貴新，黃春紅

(南寧師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,廣西 南寧 530100)

1 引言

格是一類重要的代數(shù)結(jié)構(gòu).孫中舉和方捷引入了有限格的正則圖[1]；Javaheri引入了格的余極大圖,并研究了其線圖的虧格問題[2]；Wasadikar和Survase定義了格的不可比圖，并研究了它的圍長(zhǎng)、零因子和單位的性質(zhì)[3,4].本文研究格的不可比圖的虧格.使一個(gè)圖G嵌入到拓?fù)淦矫鍿k中的最小自然數(shù)k稱為G的虧格，記作γ(G).特別地，平面圖的虧格為0.

定義1.1設(shè)E是偏序集,a,b∈E,若a≤b或b≤a，則稱a與b是可比的.若E中任何兩個(gè)元素都可比，則稱E是一個(gè)鏈.若鏈E含有n+2個(gè)元素，則稱E的長(zhǎng)度為n.

定義1.2設(shè)E是偏序集，m∈E，若對(duì)任意a∈E都有m≤a，則稱m為E的最小元，記為0.對(duì)偶地可定義E的最大元，記為1.若E中元素a滿足a≠0，且不存在b∈E使得0

定義1.3設(shè)L是偏序集，若L中任何兩個(gè)元素在L中都有上、下確界，則稱L是一個(gè)格.如果L有最大元1和最小元0，則稱L是有界的；若L中除0，1外的任一元素都只有兩個(gè)元素與之相鄰，則稱L是簡(jiǎn)單格.

定義1.4設(shè)L是格，L的不可比圖記作Γ(L)，它以L{0,1}為頂點(diǎn)集，兩個(gè)頂點(diǎn)a與b相連當(dāng)且僅當(dāng)a與b不可比.

本文中出現(xiàn)的其他的圖論和格論術(shù)語可參見[5,6].

以下所討論的格均為有限格.易知一個(gè)有界簡(jiǎn)單格L由它所含的鏈數(shù)k及各條鏈的長(zhǎng)度c1,c2,…，ck決定(不妨設(shè)c1≥c2≥…≥ck≥1),故可記L為(c1,c2,…，ck),此時(shí)L含有k個(gè)原子，于是Γ(L)含有子圖Kk.特別地，當(dāng)k=1時(shí)L=c1是一條鏈，此時(shí)Γ(L)為空?qǐng)D.故以下均設(shè)k≥2.

2 相關(guān)引理

本節(jié)給出一些引理，均是為下一節(jié)主要結(jié)果的證明作準(zhǔn)備.

引理2.1設(shè)m,n,p均為正整數(shù).

引理2.2[7]設(shè)簡(jiǎn)單連通圖G有v個(gè)頂點(diǎn)和e條邊.

引理2.3[10]若簡(jiǎn)單圖G含有9個(gè)頂點(diǎn)和33條邊，則γ(G)=3.

引理2.4[11]γ(K2,2,2,2,1)=3.

引理2.5[9]γ(K4,2,2,2)=3.

引理2.6γ(K3,3,3,1)=3.

證明因K3,3,3,1含有10個(gè)頂點(diǎn)和36條邊，故由引理2.2知γ(K3,3,3,1)≥2，注意到K3,3,3,1在S2上是不存在三角嵌入的，因而其虧格為3.

3 主要結(jié)果

設(shè)有界簡(jiǎn)單格L=(c1,c2,…,ck).若k≥9,則γ(Γ(L))≥γ(K9)=3，故當(dāng)γ(Γ(L))≤2時(shí)必有k≤8.同理可知，當(dāng)k≥8時(shí)γ(Γ(L))≥2，當(dāng)k≥5時(shí)γ(Γ(L))≥1.

定理3.1設(shè)L=(c1,c2),則

(1)γ(Γ(L))=0當(dāng)且僅當(dāng)c2≤2；

(2)γ(Γ(L))=1當(dāng)且僅當(dāng)(c1,c2)=(3,3),(4,3),(5,3),(6,3),(4,4)；

(3)γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2)=(7,3),(8,3),(9,3),(10,3),(5,4),(6,4).

證明此時(shí)Γ(L)=Kc1,c2，由引理2.1(2)即得結(jié)論.

定理3.2設(shè)L=(c1,c2,…,c8)，則γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2,…,c8)=(1,1,1,1,1,1,1,1).

定理3.3設(shè)L=(c1,c2,…,c7)，則

(1)γ(Γ(L))=1當(dāng)且僅當(dāng)(c1,c2,…,c7)=(1,1,1,1,1,1,1);

(2)γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2,…,c7)=(2,1,1,1,1,1,1).

證明如果c1≥3，則Γ(L)含有子圖K3,1,1,1,1,1,1，注意到該子圖是含有9個(gè)頂點(diǎn)和33條邊的簡(jiǎn)單圖，由引理2.3知其虧格為3，因此γ(Γ(L))≥3.

若c1=1，則Γ(L)=K7，故γ(Γ(L))=γ(K7)=1.

定理3.4設(shè)L=(c1,c2,…,c6)，則

(1)γ(Γ(L))=1當(dāng)且僅當(dāng)(c1,c2,…,c6)=(1,1,1,1,1,1)或(2,1,1,1,1,1);

(2)γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2,…,c6)=(3,1,1,1,1,1)，(4,1,1,1,1,1)或(2,2,1,1,1,1).

證明若c3≥2，則c1≥c2≥2，于是Γ(L)含有子圖K2,2,2,1,1,1，而K2,2,2,1,1,1又含有子圖K2,2,2,2,1，故由引理2.4知γ(Γ(L))≥3.因此我們只需考慮c3=1的情形.

圖1格L=(3,2,2,1,1)及Γ(L)=K3,2,2,1,1在S2中的嵌入

接著考慮c2=1的情況.

若c1≥5，則Γ(L)含有子圖K5,1,1,1,1,1，而K5,5是K5,1,1,1,1,1的子圖，因此γ(Γ(L))≥γ(K5,1,1,1,1,1)≥γ(K5,5)≥3.

若c1=4，則由引理2.2知γ(Γ(L))≥2，又注意到Γ(L)可嵌入S2(如圖2所示)，故其虧格為2.

圖2格L=(4,1,1,1,1,1)及Γ(L)=K4,1,1,1,1,1在S2中的嵌入

若c1=2，則Γ(L)=K2,1,1,1,1,1?K7，所以γ(Γ(L))=1.

若c1=1，則Γ(L)即為K6，故其虧格為1.

定理3.5設(shè)L=(c1,c2,…,c5)，則

(1)γ(Γ(L))=1當(dāng)且僅當(dāng)(c1,c2,c3,c4,c5)=(1,1,1,1,1)，(2,1,1,1,1)，(3,1,1,1,1)，(4,1,1,1,1)，(2,2,1,1,1)，(3,2,1,1,1)；

(2)γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2,c3,c4,c5)=(5,1,1,1,1)，(6,1,1,1,1)，(4,2,1,1,1)，(3,3,1,1,1)，(2,2,2,1,1)，(3,2,2,1,1).

證明如果c4≥2，則c1≥c2≥c3≥2，此時(shí)Γ(L)含K2,2,2,2,1作為子圖，而由引理2.4知γ(K2,2,2,2,1)=3，所以γ(Γ(L))≥3.故c4=c5=1.

若c3≥3，則c1≥c2≥3，此時(shí)Γ(L)含K3,3,3,1,1作為子圖，而K6,5?K3,3,3,1,1，所以γ(Γ(L))≥γ(K6,5)=3.因此c3≤2.

當(dāng)c3=2時(shí)，若c2≥3，則K3,3,2,1,1?Γ(L)，但K5,5?K3,3,2,1,1，所以γ(Γ(L))≥γ(K5,5)=3，故c2=2.若c1≥4，則K5,5?K4,2,2,1,1?Γ(L)，進(jìn)而有γ(Γ(L))≥γ(K5,5)=3.

最后考慮c3=1的情況.

若c2≥4，則K6,5?K4,4,1,1,1?Γ(L)，而若c2=3且c1≥4，則有K5,5?K4,3,1,1,1?Γ(L)，于是都有γ(Γ(L))≥3，而圖3給出了K3,3,1,1,1在S2上的嵌入，所以γ(K3,3,1,1,1)=2.當(dāng)c2=3時(shí)，c1=3.

圖3格L=(3,3,1,1,1)及Γ(L)=K3,3,1,1,1在S2中的嵌入

圖4格L=(3,2,1,1,1)及Γ(L)=K3,2,1,1,1在S1中的嵌入

圖5格L=(4,1,1,1,1)及Γ(L)=K4,1,1,1,1在S1中的嵌入

圖6格L=(6,1,1,1,1)及Γ(L)=K6,1,1,1,1在S2中的嵌入

定理3.6設(shè)L=(c1,c2,c3,c4)，則

(1)γ(Γ(L))=0當(dāng)且僅當(dāng)(c1,c2,c3,c4)=(1,1,1,1)，(2,1,1,1)；

(2)γ(Γ(L))=1當(dāng)且僅當(dāng)(c1,c2,c3,c4)=(c1,1,1,1)(其中3≤c1≤6)，(2,2,1,1)，(3,2,1,1)，(4,2,1,1),(3,3,1,1)，(2,2,2,1)，(2,2,2,1)，(3,2,2,1)，(2,2,2,2)；

(3)γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2,c3,c4)=(c1,1,1,1)(其中7≤c1≤10)，(5,2,1,1)，(6,2,1,1)，(4,3,1,1)，(4,2,2,1)，(3,3,2,1)，(3,2,2,2).

證明若c4≥3，則K6,6?K3,3,3,3?Γ(L)，這使得γ(Γ(L))≥γ(K6,6)≥3，故c4≤2.

接下來考慮c4=1的情形.

由引理2.6知c3≤2，否則Γ(L)含K3,3,3,1作為子圖，使得γ(Γ(L))≥3.

情形1c3=2.

若c2≥4，則有K6,5?K4,4,2,1?Γ(L)，進(jìn)而γ(Γ(L))≥3.

若c2=3，則c1=3，否則K5,5?K4,3,2,1?Γ(L)，從而γ(Γ(L))≥3.而c1=3，此時(shí)Γ(L)=K3,3,2,1.由于K5,4?K3,3,2,1?K3,3,1,1,1，因此γ(K3,3,2,1)=2.

若c2=2，則c1≤4，否則γ(Γ(L))≥γ(K5,2,2,1)≥γ(K5,5)=3.又因?yàn)镵3,3?K2,2,1,1?K3,2,1,1?K3,1,1,1,1，故γ(K2,2,2,1)=γ(K3,2,2,1)=1.

情形2c3=1.

顯然c2≥4是不成立的，因?yàn)镵5,5?K4,4,1,1?Γ(L),這使得γ(Γ(L))≥3，故c2≤3.

當(dāng)c2=3時(shí)c1∈{3,4}，否則K5,5?K5,3,1,1?Γ(L)，即γ(Γ(L))≥γ(K5,5)≥3，所以c1=3或4.一方面由于K4,4?K3,3,1,1，而K5,4?K4,3,1,1，另一方面因?yàn)镵3,3,1,1?K3,2,1,1,1，K4,3,1,1?K4,2,1,1,1，所以γ(K3,3,1,1)=1，γ(K4,3,1,1)=2.

當(dāng)c2=2時(shí)，易知c1≥7是不成立的，因?yàn)镵7,4?K7,2,1,1?Γ(L)，這使得γ(Γ(L))≥3.故2≤c1≤6.再因?yàn)镵3,3?K2,2,1,1?K3,2,1,1?K3,1,1,1,1，K4,4?K4,2,1,1?K4,1,1,1,1，K5,4?K5,2,1,1?K6,2,1,1?K6,1,1,1,1，因此γ(K2,2,1,1)=γ(K3,2,1,1)=γ(K4,2,1,1)=1，γ(K5,2,1,1)=γ(K6,2,1,1)=2.

當(dāng)c2=1時(shí)，若c1≥11，則K11,3?K11,1,1,1?Γ(L)，導(dǎo)致γ(Γ(L))≥3，故c1≤10.若1≤c1≤2，則Γ(L)是平面圖，即γ(Γ(L))=0.若3≤c1≤6，則Γ(L)=Kc1,1,1，故有K3,3?K3,1,1,1?K4,1,1,1?K5,1,1,1?K6,1,1,1，且圖7給出K6,1,1,1在S1上的嵌入，故γ(Γ(L))=1.同理，若7≤c1≤10，則K7,3?K7,1,1,1?K8,1,1,1?K9,1,1,1?K10,1,1,1，且圖8給出K10,1,1,1在S2上的嵌入，故γ(Γ(L))=2.

圖7格L=(6,1,1,1)及Γ(L)=K6,1,1,1在S1中的嵌入

圖8格L=(10,1,1,1)及Γ(L)=K10,1,1,1在S2中的嵌入

定理3.7設(shè)L=(c1,c2,c3)，則

(1)γ(Γ(L))=0當(dāng)且僅當(dāng)(c1,c2,c3)=(c1,1,1),(2,1,1),(2,2,2),c1≥1；

(2)γ(Γ(L))=1當(dāng)且僅當(dāng)(c1,c2,c3)=(3,2,1)，(4,2,1)，(5,2,1)，(6,2,1)，(3,3,1)，(4,3,1)，(3,2,2)，(4,2,2)，(3,3,2)，(3,3,3)；

(3)γ(Γ(L))=2當(dāng)且僅當(dāng)(c1,c2,c3)=(7,2,1)，(8,2,1)，(9,2,1)，(10,2,1)，(5,3,1)，(6,3,1)，(4,4,1)，(5,2,2)，(6,2,2)，(4,3,2)，(4,4,2)，(4,4,3).

證明若c1≥c2≥c3≥4，則有K8,4?K4,4,4?Γ(L)，從而γ(Γ(L))≥γ(K4,4,4)≥γ(K8,4)=3，故c3≤3.

情形1c3=3.若c2≥4，則K7,4?K4,4,3?Γ(L)，即γ(Γ(L))≥3.因此c2≤3.此時(shí)令c2=3，則當(dāng)c1≥5時(shí)有K6,5?K5,3,3?Γ(L)，這使得γ(Γ(L))≥3.故c1∈{3,4}，于是由引理2.1(4)知γ(K3,3,3)=1，γ(K4,3,3)=2.

情形2c3=2.顯然c2≤4.否則K7,5?K5,5,2?Γ(L)，導(dǎo)致γ(Γ(L))≥3.

情形2.1c2=4.若c1≥5，則有γ(Γ(L))≥γ(K5,4,2)≥γ(K6,5)=3.而由引理2.1(4)知γ(K4,4,2)=2.

情形2.2c2=3.若c1≥5，則K5,5?K5,3,2?Γ(L)，故有γ(Γ(L))≥3,所以c1≤4.再由引理1(4)知γ(K4,3,2)=2,γ(K3,3,2)=1.

情形2.3c2=2.若c1≥7，則γ(Γ(L))≥3,故c1≤6.由引理2.1(4)可得γ(K2,2,2)=0，γ(K3,2,2)=γ(K4,2,2)=1，γ(K5,2,2)=γ(K6,2,2)=2.

情形3c3=1.易知c2≥5時(shí)，K6,5?K5,5,1?Γ(L)，從而γ(Γ(L))≥3，故c2≤4.

情形3.1c2=4.若c1≥5，則K5,4,1?Γ(L)，即γ(Γ(L))≥3，因此c1=4.由引理2.1(4)知γ(K4,4,1)=2.

情形3.2c2=3.如果c1≥7，則K7,4?K7,3,1?Γ(L)，導(dǎo)致γ(Γ(L))≥3.所以c1≤6.若c1≤5，則由引理2.1(4)可知γ(K5,3,1)=2，γ(K4,3,1)=γ(K3,3,1)=1.而若c1=6，則K6,4?K6,3,1?K6,1,1,1,1，且γ(K6,1,1,1,1)=2,因此γ(K6,3,1)=2.

情形3.3c2=2.顯然c1≥11是不可能的，否則K11,3?K11,2,1?Γ(L)，從而γ(Γ(L))≥3，故c1≤10.若c1≤5，則由引理2.1(4)可知γ(K5,2,1)=γ(K4,2,1)=γ(K3,2,1)=1，γ(K2,2,1)=0.而若c1=6，則Γ(L)=K6,2,1，且K6,3?K6,2,1?K6,1,1,1，故γ(Γ(L))=1.又因?yàn)镵7,3?K7,2,1，故γ(K7,2,1)≥2.另一方面，因?yàn)镵7,2,1?K8,2,1?K9,2,1?K10,2,1?K10,1,1,1，故γ(K7,2,1)=γ(K8,2,1)=γ(K9,2,1)=γ(K10,2,1)=2.

情形3.4c2=1.此時(shí)Γ(L)=Km,1,1顯然是平面圖，從而γ(Γ(L))=0.

4 結(jié)束語

本文確定了虧格小于3的有界簡(jiǎn)單格的結(jié)構(gòu).接下來我們將繼續(xù)研究一般格的虧格問題，同時(shí)也將研究關(guān)于格的不可比圖的其他問題，如正則性、團(tuán)數(shù)的計(jì)算等.