具有正則圖的有限格的一些注記

孫中舉，方捷，2

(1.汕頭大學(xué)數(shù)學(xué)系，廣東汕頭515063；2.廣東技術(shù)師范學(xué)院計(jì)算機(jī)學(xué)院，廣東廣州510665)

具有正則圖的有限格的一些注記

孫中舉1，方捷1，2

(1.汕頭大學(xué)數(shù)學(xué)系，廣東汕頭515063；2.廣東技術(shù)師范學(xué)院計(jì)算機(jī)學(xué)院，廣東廣州510665)

研究了一類具有正則圖的有限格，稱之為正則圖格.證明了一個有限格是分配的正則圖格當(dāng)且僅當(dāng)它是布爾格，同時找出了所有1階和2階的正則圖格.特別地，證明了8-元素布爾格是最小的3階正則圖格.

正則圖；格；布爾格

0 引言

格是一類重要的有序代數(shù)，一直以來，人們用哈斯圖來表示有序集.由于哈斯圖直觀簡潔，因而被廣泛地應(yīng)用到格論與有序代數(shù)的研究中，格的很多性質(zhì)都可以很好地反映在哈斯圖中.傳統(tǒng)的研究都側(cè)重于格的代數(shù)性質(zhì)，忽視了格的哈斯圖的圖的性質(zhì)，目前還沒有什么文獻(xiàn)研究格的圖的性質(zhì).在圖論中，頂點(diǎn)所連的邊數(shù)稱為該頂點(diǎn)的度，所有頂點(diǎn)的度都相等的圖稱為正則圖.關(guān)于圖的詳細(xì)知識，可參看李建中等的譯著[1].本文將正則圖和有限格結(jié)合起來，研究哈斯圖是正則圖的有限格，稱之為正則圖格.

1 定義和基本性質(zhì)

定義設(shè)L是一個有限格.如果L的哈斯圖是正則圖，那么稱L是一個正則圖格.如果L的哈斯圖中每個點(diǎn)的度都是n，那么稱L是一個n階正則圖格.

由定義可知2階布爾格是2階正則圖格，3階布爾格是3階正則圖格.

注意到哈斯圖中的邊表示的是有序集的覆蓋關(guān)系.若點(diǎn)a覆蓋點(diǎn)b，則對任意的x∈[a，b]，有x＝a或x＝b.設(shè)L是一個n階正則圖格，對于其中任意一元素x，由定義可知x覆蓋k個點(diǎn)，且被n-k個點(diǎn)覆蓋，0≤k≤n.如圖1所示，3階布爾格L1是3階正則圖格，其中點(diǎn)x覆蓋兩個點(diǎn)y和z，且被一個最大點(diǎn)1覆蓋.在哈斯圖中，我們把覆蓋點(diǎn)a的所有點(diǎn)的個數(shù)稱為點(diǎn)a的上度,把被a覆蓋的點(diǎn)的個數(shù)稱為點(diǎn)a的下度.例如，圖1的3階布爾格中的點(diǎn)x的度是3，上度是1，下度是2.

圖13 階布爾格

引理1設(shè)L1和L2是有限格.對任意的a1∈L1及a2∈L2，如果a1在L1中的度是m1，a2在L2中的度是m2，那么（a1，a2）在L1×L2中的度是m1+m2.

證明設(shè)a1在L1中被p個點(diǎn)覆蓋，它們是x1，x2，…，xp；a1覆蓋q個點(diǎn)，它們是y1，y2，…，yq；設(shè)a2在L2中被r個點(diǎn)覆蓋，它們是z1，z2，…，zr；a2覆蓋s個點(diǎn)，它們是w1，w2，…，ws.因?yàn)閍1在L1中的度是m1，a2在L2中的度是m2,所以p+q=m1，r+s=m2.于是在L1×L2中，（a1，a2）被（x1，a2），（x2，a2），…，（xp，a2），（a1，z1），（a1，z2），…，（a1，zr）這p+r個點(diǎn)覆蓋，所以（a1，a2）在L1×L2中的上度是p+r.因?yàn)樵贚1×L2中，（a1，a2）覆蓋（y1，a2），（y2，a2），…，（yq，a2），（a1，w1），（a1，w2），…，（a1，ws）這q+s個點(diǎn)，所以（a1，a2）在L1×L2中的下度是q+s.于是（a1，a2）在L1×L2中的度是（p+r）+（q+s）=m1+m2.證畢.

定理1設(shè)L，L1，L2是有限格，而且L?L1×L2，則L是正則圖格當(dāng)且僅當(dāng)L1和L2都是正則圖格.

證明（?）設(shè)L1是n1階正則圖格，L2是n2階正則圖格，則由引理1可得，L1×L2中的每一點(diǎn)的度都是n1+n2，所以L?L1×L2是n1+n2階正則圖格.

（?）現(xiàn)在L?L1×L2是正則圖格.假設(shè)L1或L2不是正則圖格，不妨設(shè)L1不是正則圖格，則由正則圖格的定義知存在a，b∈L1，使得a和b的度不相等.記它們的度分別為ma和mb，則ma≠mb.設(shè)c是L2中任一元素，它在L2中的度是mc.于是由引理1可知，在L1×L2中，（a，c）的度是ma+mc，（b，c）的度是mb+mc.因?yàn)閙a≠mb，所以ma+mc≠mb+mc，于是（a，c）和（b，c）的度不相等，這與L?L1×L2是正則圖格矛盾，從而推知L1和L2都是正則圖格.證畢.

推論1若L1和L2分別是n1階和n2階正則圖格，則L1×L2是n1+n2階正則圖格.

證明由引理1和定理1立即可得.

推論2設(shè)L，L1，L2，…，Ln是有限格，而且L?L1×L2×…×Ln，則L是正則圖格當(dāng)且僅當(dāng)L1，L2，…，Ln都是正則圖格.

2 正則圖格與布爾格

設(shè)L是一個具有最小元素0的格，a∈L，稱a是L的一個原子，若a覆蓋最小元素0.我們知道，有限的布爾格是由有限個原子所生成，由n個原子所生成的布爾格的元素個數(shù)為2n.我們將用2n表示這樣的一個n階布爾格.

定理2有限的布爾格是正則圖格.

為了后面的需要，我們給出下面引理.

引理2設(shè)L是一個有限的分配格，a是一個原子，又設(shè)b∈L.若a∧b＝0，則a∨b覆蓋b.

證明首先證a∨b≠b.假若a∨b=b，則a≤b，于是a=a∧b.由于條件中a∧b＝0，所以a＝0，這與a是原子矛盾，所以a∨b≠b.

其次，?x∈L，如果b≤x≤a∨b，那么x=x∧（a∨b）＝（x∨b）∧（a∨b）＝（x∧a）∨b.因?yàn)閍是原子，所以x∧a＝0或x∧a＝a.前者給出x=（x∧a）∨b＝b，后者給出x=（x∧a）∨b＝a∨b.由此推知a∨b覆蓋b.證畢.

定理3設(shè)L是一個有限格，則L是分配的正則圖格當(dāng)且僅當(dāng)L是布爾格.

證明由定理2，即得充分性.現(xiàn)證必要性.

設(shè)L是n階正則圖格，則L恰好有n個原子，記為a1，a2，…，an.設(shè)c=a1∨因?yàn)長是分配格且a1，a2，…，an是原子，所以對c.由于ai∧bi=0且ai是原子，所以由引理2可得c=ai∨bi覆蓋bi，于是c覆蓋b1，b2，…，bn.因?yàn)閕≠j蘊(yùn)涵ai∧bj=ai∧（ai∨…）=ai≠0，ai∧bi=0，所以i≠j蘊(yùn)涵bi≠bj，于是c至少覆蓋n個不同元素b1，b2，…，bn，從而c的下度至少是n.又因?yàn)長是n階正則圖格，只有最大元1的下度不小于n，所以c=1，于是a1∨a2∨…∨an=c=1.因?yàn)閍1，a2，…，an是原子，所以?x∈L，x=x∧1=x∧（a1∨a2∨…∨an）=（x∧a1）∨（x∧a2）∨…∨（x∧an）=ai1∨ai2∨…∨aik，其中i1，i2，…，in是1，2，…，n的某個排列，0≤k≤n.此時x有互補(bǔ)元y=aik+1∨aik+2∨…∨ain.于是L是一個有限的由原子生成的分配格，它的任一元素都有補(bǔ)元，所以L是布爾格.證畢.

3 低階的正則圖格

定理4我們有下面論斷：

1）1階正則圖格有且只有一個2元素格；

2）2階正則圖格是具有如圖2形式的圈.

圖22 階正則圖格

證明1）由1階正則圖格的定義立即可得.

2）設(shè)L是2階正則圖格，則L有且僅有兩個原子，這兩個原子的下度是1，上度也必須是1.L中除了最大元1和最小元0，其它元素的上度和下度都是1，所以2階正則圖格是具有上面形式的圈.證畢.

推論32階布爾格是最小的2階正則圖格.

我們知道，一個格L上所有同余關(guān)系的集合是一個完全的分配格[2]，記為ConL.當(dāng)L是一個有限分配格時，ConL是一個布爾格.因此，下面來自于Peter Jipsen等[2]的引理是顯然的.

引理3若L是n元素鏈，則L的同余格ConL?2n-1.

設(shè)P，Q是兩個有序集，且P有最大元α，Q有最小元β.定義P與Q的直和P⊕ˉQ如下：

設(shè)L是一個格，又設(shè)a，b∈L且a≤b.通常用θ（a，b）表示由{a，b}生成的最小同余，稱為恒等a，b的L的主同余.文中所用相關(guān)術(shù)語與Blyth著作[3]中的相同.

稱格L的一個子格I為理想，若x≤a∈I蘊(yùn)涵x∈I，記θ（I）為由I所生成的最小同余.記Ω（L）＝{θ（I）I是L的理想}.有如下結(jié)果.表示L中元素的個數(shù).

證明因?yàn)長是2階正則圖格，所以由定理4可知，L有如圖3的形式.

證明因?yàn)長是2階正則圖格，所以由定理4可知L是如圖3所示的一個圈.于是L的理想I有4種可能：

1）若I＝{0}，則θ（I）=ω（相等關(guān)系）；

4）若I＝L，則θ（I）=.

圖3 一般2階正則圖格

由定理1的推論1可知，1階正則圖格和2階正則圖格的直積是3階正則圖格，但3階正則圖格未必都是1階正則圖格和2階正則圖格的直積.圖4給出兩個3階正則圖格，其中L1是1階正則圖格和2階正則圖格的直積，而L2不可分解，故不可能是1階正則圖格和2階正則圖格的直積.

定理73階布爾格是最小的3階正則圖格.

證明設(shè)L是3階正則圖格，則其最小元0被3個元素所覆蓋，記為a，b，c.這3個元素的下度均是1，上度均是2；其最大元1覆蓋3個元素，記為x，y，z.這3個元素的上度均是1，下度均是2.于是L至少有8個元素.注意到最小元0僅被a，b，c所覆蓋及最大元1僅覆蓋x，y，z，故知由0，1，a，b，c，x，y，z所生成的L的子格為如圖5所示的3階布爾格.因而可推知，3階布爾格是最小的3階正則圖格.證畢.

關(guān)于高階的正則圖格，結(jié)果比較復(fù)雜，目前還沒有很好的結(jié)果，不過我們有如下猜想，歡迎有興趣的同行能證明此猜想.

猜想對任意正整數(shù)n，n階布爾格是最小的n階正則圖格.

圖4 可分解和不可分解的3階正則圖格

圖5 最小的3階正則圖格

[1] West D B.圖論導(dǎo)引[M].李建中，駱吉洲，譯.北京：機(jī)械工業(yè)出版社，2006.

[2] Jipsen P，Rose H.Varieties of latt ices[M]//Lect ure Not es in Mat hematics.Berlin：Springer Verlag Press，1992.

[3] Blyth T S，Varlet J C.Ockham algebras[M].Oxford：Oxford University Press，1994.

[4] Davey B A.On the lattice of subvariet ies[J].Houst on J Math，1979（5）：183-192.

[5] Sankappanavar H P.A course in universal algebra[M].New York：Springer Verlag Press，1981.

Some Remarks on Regular Graph Lattices

SUN Zhong-ju1，F(xiàn)ANG Jie2

(1.Department of Mathematics,Shantou University，Shantou 515063，Guangdong，China;2.School of Computer Science,Guangdong Polytechnic Normal University,Guangzhou 510665,Guangdong，China)

A regular graph lattice is a lattice whose Hass diagram is a regular graph.It is shown that a finite distributive lattice is a regular graph lattice if and only if it is a Booleanlattice.All the 1-degree graph lattices and 2-degreegraph lattices are found.It is shown that the 8-element Booleanlattice is thesmallest 3-degree regulargraph lattice.

regular graph；lattice；Boolean lattice

O 153.1；O 153.2；O 153.5

A

1001-4217（2010）02-0011-05

2009-11-03

孫中舉（1982-），男,湖北蘄春人，博士研究生.研究方向：格論與有序代數(shù).E-mail：g_zjsun@stu.edu.cn