具有正则图的有限格的一些注记

孙中举，方捷，2

(1.汕头大学数学系，广东汕头515063；2.广东技术师范学院计算机学院，广东广州510665)

具有正则图的有限格的一些注记

孙中举1，方捷1，2

(1.汕头大学数学系，广东汕头515063；2.广东技术师范学院计算机学院，广东广州510665)

研究了一类具有正则图的有限格，称之为正则图格.证明了一个有限格是分配的正则图格当且仅当它是布尔格，同时找出了所有1阶和2阶的正则图格.特别地，证明了8-元素布尔格是最小的3阶正则图格.

正则图；格；布尔格

0 引言

格是一类重要的有序代数，一直以来，人们用哈斯图来表示有序集.由于哈斯图直观简洁，因而被广泛地应用到格论与有序代数的研究中，格的很多性质都可以很好地反映在哈斯图中.传统的研究都侧重于格的代数性质，忽视了格的哈斯图的图的性质，目前还没有什么文献研究格的图的性质.在图论中，顶点所连的边数称为该顶点的度，所有顶点的度都相等的图称为正则图.关于图的详细知识，可参看李建中等的译著[1].本文将正则图和有限格结合起来，研究哈斯图是正则图的有限格，称之为正则图格.

1 定义和基本性质

定义设L是一个有限格.如果L的哈斯图是正则图，那么称L是一个正则图格.如果L的哈斯图中每个点的度都是n，那么称L是一个n阶正则图格.

由定义可知2阶布尔格是2阶正则图格，3阶布尔格是3阶正则图格.

注意到哈斯图中的边表示的是有序集的覆盖关系.若点a覆盖点b，则对任意的x∈[a，b]，有x＝a或x＝b.设L是一个n阶正则图格，对于其中任意一元素x，由定义可知x覆盖k个点，且被n-k个点覆盖，0≤k≤n.如图1所示，3阶布尔格L1是3阶正则图格，其中点x覆盖两个点y和z，且被一个最大点1覆盖.在哈斯图中，我们把覆盖点a的所有点的个数称为点a的上度,把被a覆盖的点的个数称为点a的下度.例如，图1的3阶布尔格中的点x的度是3，上度是1，下度是2.

图13 阶布尔格

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

证明设a1在L1中被p个点覆盖，它们是x1，x2，…，xp；a1覆盖q个点，它们是y1，y2，…，yq；设a2在L2中被r个点覆盖，它们是z1，z2，…，zr；a2覆盖s个点，它们是w1，w2，…，ws.因为a1在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个点覆盖，所以（a1，a2）在L1×L2中的上度是p+r.因为在L1×L2中，（a1，a2）覆盖（y1，a2），（y2，a2），…，（yq，a2），（a1，w1），（a1，w2），…，（a1，ws）这q+s个点，所以（a1，a2）在L1×L2中的下度是q+s.于是（a1，a2）在L1×L2中的度是（p+r）+（q+s）=m1+m2.证毕.

定理1设L，L1，L2是有限格，而且L≅L1×L2，则L是正则图格当且仅当L1和L2都是正则图格.

证明（⇐）设L1是n1阶正则图格，L2是n2阶正则图格，则由引理1可得，L1×L2中的每一点的度都是n1+n2，所以L≅L1×L2是n1+n2阶正则图格.

（⇒）现在L≅L1×L2是正则图格.假设L1或L2不是正则图格，不妨设L1不是正则图格，则由正则图格的定义知存在a，b∈L1，使得a和b的度不相等.记它们的度分别为ma和mb，则ma≠mb.设c是L2中任一元素，它在L2中的度是mc.于是由引理1可知，在L1×L2中，（a，c）的度是ma+mc，（b，c）的度是mb+mc.因为ma≠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设L，L1，L2，…，Ln是有限格，而且L≅L1×L2×…×Ln，则L是正则图格当且仅当L1，L2，…，Ln都是正则图格.

2 正则图格与布尔格

设L是一个具有最小元素0的格，a∈L，称a是L的一个原子，若a覆盖最小元素0.我们知道，有限的布尔格是由有限个原子所生成，由n个原子所生成的布尔格的元素个数为2n.我们将用2n表示这样的一个n阶布尔格.

定理2有限的布尔格是正则图格.

为了后面的需要，我们给出下面引理.

引理2设L是一个有限的分配格，a是一个原子，又设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.因为a是原子，所以x∧a＝0或x∧a＝a.前者给出x=（x∧a）∨b＝b，后者给出x=（x∧a）∨b＝a∨b.由此推知a∨b覆盖b.证毕.

定理3设L是一个有限格，则L是分配的正则图格当且仅当L是布尔格.

证明由定理2，即得充分性.现证必要性.

设L是n阶正则图格，则L恰好有n个原子，记为a1，a2，…，an.设c=a1∨因为L是分配格且a1，a2，…，an是原子，所以对c.由于ai∧bi=0且ai是原子，所以由引理2可得c=ai∨bi覆盖bi，于是c覆盖b1，b2，…，bn.因为i≠j蕴涵ai∧bj=ai∧（ai∨…）=ai≠0，ai∧bi=0，所以i≠j蕴涵bi≠bj，于是c至少覆盖n个不同元素b1，b2，…，bn，从而c的下度至少是n.又因为L是n阶正则图格，只有最大元1的下度不小于n，所以c=1，于是a1∨a2∨…∨an=c=1.因为a1，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有互补元y=aik+1∨aik+2∨…∨ain.于是L是一个有限的由原子生成的分配格，它的任一元素都有补元，所以L是布尔格.证毕.

3 低阶的正则图格

定理4我们有下面论断：

1）1阶正则图格有且只有一个2元素格；

2）2阶正则图格是具有如图2形式的圈.

图22 阶正则图格

证明1）由1阶正则图格的定义立即可得.

2）设L是2阶正则图格，则L有且仅有两个原子，这两个原子的下度是1，上度也必须是1.L中除了最大元1和最小元0，其它元素的上度和下度都是1，所以2阶正则图格是具有上面形式的圈.证毕.

推论32阶布尔格是最小的2阶正则图格.

我们知道，一个格L上所有同余关系的集合是一个完全的分配格[2]，记为ConL.当L是一个有限分配格时，ConL是一个布尔格.因此，下面来自于Peter Jipsen等[2]的引理是显然的.

引理3若L是n元素链，则L的同余格ConL≅2n-1.

设P，Q是两个有序集，且P有最大元α，Q有最小元β.定义P与Q的直和P⊕¯Q如下：

设L是一个格，又设a，b∈L且a≤b.通常用θ（a，b）表示由{a，b}生成的最小同余，称为恒等a，b的L的主同余.文中所用相关术语与Blyth著作[3]中的相同.

称格L的一个子格I为理想，若x≤a∈I蕴涵x∈I，记θ（I）为由I所生成的最小同余.记Ω（L）＝{θ（I）I是L的理想}.有如下结果.表示L中元素的个数.

证明因为L是2阶正则图格，所以由定理4可知，L有如图3的形式.

证明因为L是2阶正则图格，所以由定理4可知L是如图3所示的一个圈.于是L的理想I有4种可能：

1）若I＝{0}，则θ（I）=ω（相等关系）；

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

图3 一般2阶正则图格

由定理1的推论1可知，1阶正则图格和2阶正则图格的直积是3阶正则图格，但3阶正则图格未必都是1阶正则图格和2阶正则图格的直积.图4给出两个3阶正则图格，其中L1是1阶正则图格和2阶正则图格的直积，而L2不可分解，故不可能是1阶正则图格和2阶正则图格的直积.

定理73阶布尔格是最小的3阶正则图格.

证明设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阶正则图格.证毕.

关于高阶的正则图格，结果比较复杂，目前还没有很好的结果，不过我们有如下猜想，欢迎有兴趣的同行能证明此猜想.

猜想对任意正整数n，n阶布尔格是最小的n阶正则图格.

图4 可分解和不可分解的3阶正则图格

图5 最小的3阶正则图格

[1] West D B.图论导引[M].李建中，骆吉洲，译.北京：机械工业出版社，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，FANG 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-），男,湖北蕲春人，博士研究生.研究方向：格论与有序代数.E-mail：g_zjsun@stu.edu.cn