文档库

最新最全的文档下载
当前位置:文档库 > 具有正则图的有限格的一些注记

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

收稿日期:2009-11-03

作者简介:孙中举(1982-),男,湖北蕲春人,博士研究生.研究方向:格论与有序代数.

E -mail :g_zjsun@http://www.wendangku.net/doc/ecc7261ca76e58fafab00344.html

2010年5月

汕头大学学报(自然科学版)第25卷第2期May 2010Journal of Shantou University (Natural Science )Vol .25No .2z x 1y 0L 1图13阶布尔格文章编号:1001-4217(2010)02-0011-05

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

孙中举1,方

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

摘要:研究了一类具有正则图的有限格,称之为正则图格.证明了一个有限格是分配的正

则图格当且仅当它是布尔格,同时找出了所有1阶和2阶的正则图格.特别地,证明了8-元

素布尔格是最小的3阶正则图格.

关键词:正则图;格;布尔格

中图分类号:O 153.1;O 153.2;O 153.5文献标识码:A

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阶布尔格L 1是3阶正则图格,其中点x 覆盖两个点y 和z ,且被一个最大点1覆盖.在哈

斯图中,我们把覆盖点a 的所有点的个数称为点a 的上度,

把被a 覆盖的点的个数称为点a 的下度.例如,图1的3阶布尔格中的点x 的度是3,上度是1,下度是2.引理1

设L 1和L 2是有限格.对任意的a 1∈L 1及a 2∈L 2,如果a 1在L 1中的度是m 1,a 2在L 2中的度是m 2,那么(a 1,a 2)在L 1×L 2中的度是m 1+m 2.

证明设a 1在L 1中被p 个点覆盖,它们是x 1,x 2,…,x p ;a 1覆盖q 个点,它们

是y 1,y 2,…,y q ;设a 2在L 2中被r 个点覆盖,它们是z 1,z 2,…,z r ;a 2覆盖s 个点,它们是w 1,w 2,…,w s .因为a 1在L 1中的度是m 1,a 2在L 2中的度是m 2,所以p +q =m 1,r +s =m 2.于是在L 1×L 2中,(a 1,a 2)被(x 1,a 2),(x 2,a 2),…,(x p ,a 2),(a 1,z 1),(a 1,z 2),…,(a 1,z r )这p +r 个点覆盖,所以(a 1,a 2)在L 1×L 2中的上度是p +r .因为在L 1×L 2中,(a 1,a 2)覆盖(y 1,a 2),(y 2,a 2),…,(y q ,a 2),(a 1,w 1),(a 1,w 2),…,(a 1,w s )这q +s 个点,所以(a 1,a 2)在L 1×L 2中的下度是q +s .于是(a 1,a 2)在L 1×L 2中的度是(p +r )+(q +s )=m 1+m 2.证毕.

定理1设L ,L 1,L 2是有限格,而且L 艿L 1×L 2,则L 是正则图格当且仅当L 1和L 2都是正则图格.

证明(坩)设L 1是n 1阶正则图格,L 2是n 2阶正则图格,则由引理1可得,L 1×L 2中的每一点的度都是n 1+n 2,所以L 艿L 1×L 2是n 1+n 2阶正则图格.

(圯)现在L 艿L 1×L 2是正则图格.假设L 1或L 2不是正则图格,不妨设L 1不是正则图格,则由正则图格的定义知存在a ,b ∈L 1,使得a 和b 的度不相等.记它们的度分别为m a 和m b ,则m a ≠m b .设c 是L 2中任一元素,它在L 2中的度是m c .于是由引理1可知,在L 1×L 2中,(a ,c )的度是m a +m c ,(b ,c )的度是m b +m c .因为m a ≠m b ,所以m a +m c ≠m b +m c ,于是(a ,c )和(b ,c )的度不相等,这与L 艿L 1×L 2是正则图格矛盾,从而推知L 1和L 2都是正则图格.证毕.

推论1若L 1和L 2分别是n 1阶和n 2阶正则图格,则L 1×L 2是n 1+n 2阶正则图格.证明由引理1和定理1立即可得.

推论2设L ,L 1,L 2,…,L n 是有限格,而且L 艿L 1×L 2×…×L n ,则L 是正则图格当且仅当L 1,L 2,…,L n 都是正则图格.

2正则图格与布尔格

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

定理2

有限的布尔格是正则图格.证明设L 是一个有限的布尔格,则L 艿2n ,其中2={0,1}是2元素格,它是1阶正则图格,n 是一个正整数.于是L 同构于n 个正则图格的直积,由定理1可得L 也是正则图格.证毕.

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

引理2设L 是一个有限的分配格,a 是一个原子,又设b ∈L .若a ∧b =0,则汕头大学学报(自然科学版)第25卷12

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 个原子,记为a 1,a 2,…,a n .设c =a 1∨a 2∨…∨a n ,b i =∨j ≠i

a j =a 1∨a 2∨…a i -1∨a i +1∨…∨a n ,1≤i ≤n .因为L 是分配格且a 1,a 2,…,a n 是原子,所以对1≤i ≤n ,a i ∧

b i =a i ∧(∨j ≠i a j )=∨j ≠i

(a i ∧a j )=0,a i ∨b i =c .由于a i ∧b i =0且a i 是原子,所以由引理2可得c =a i ∨b i 覆盖b i ,于是c 覆盖b 1,b 2,…,b n .因为i ≠j 蕴涵a i ∧b j =a i ∧(a i ∨…)=a i ≠0,a i ∧b i =0,所以i ≠j 蕴涵b i ≠b j ,于是c 至少覆盖n 个不同元素b 1,b 2,…,b n ,从而c 的下度至少是n .又因为L 是n 阶正则图格,只有最大元1的下度不小于n ,所以c =1,于是a 1∨a 2∨…∨a n =c =1.因为a 1,a 2,…,a n 是原子,所以坌x ∈L ,x =x ∧1=x ∧(a 1∨a 2∨…∨a n )=(x ∧a 1)∨(x ∧a 2)∨…∨(x ∧a n )=a i 1∨a i 2∨…∨a i k

,其中i 1,i 2,…,i n 是1,2,…,n 的某个排列,0≤k ≤n .此时x 有互补元y =a i k +1∨a i k +2∨…∨a i n

.于是L 是一个有限的由原子生成的分配格,它的任一元素都有补元,所以L 是布尔格.证毕.

3低阶的正则图格

定理4我们有下面论断:

1)1阶正则图格有且只有一个2元素格;

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

证明

1)由1阶正则图格的定义立即可得.

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

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

我们知道,一个格L 上所有同余关系的集合是一个完全的分配格[2],记为Con L .当L 是一个有限分配格时,Con L 是一个布尔格.因此,下面来自于Peter Jipsen 等[2]孙中举等:具有正则图的有限格的一些注记第2

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

期···

图22阶正则图格13

…1

a m

a m -1a 3

a 2

a 1

0b 1b 2b n -2b n -1

b n 图3一般2阶正则图格

的引理是显然的.

引理3若L 是n 元素链,则L 的同余格Con L 艿2n -1.

设P ,Q 是两个有序集,且P 有最大元α,Q 有最小元β.定义P 与Q 的直和P 茌

軘Q 如下:

P 茌

軘Q ={x x ∈P ∪Q ,α≡β}.设L 是一个格,又设a ,b ∈L 且a ≤b .通常用θ(a ,b )表示由{a ,b }生成的最小同余,称为恒等a ,b 的L 的主同余.文中所用相关术语与Blyth 著作[3]中的相同.

定理5如果L 是2阶正则图格,那么L 的同余格Con L 艿2

L -4茌軘22,其中L 表示L 中元素的个数.

证明

因为L 是2阶正则图格,所以由定理4可知,L 有如图3的形式.这里L =m +n +2.设L 1表示链a 1≤a 2≤…≤a m ,L 2

表示链b 1≤b 2≤…≤b n .则由引理3知,Con L 1艿2m -1,Con L 2艿2n -1.因为在L 中,θ(0,a 1)=θ(b 1,1)=θ(0,a m )=θ(b n ,1),θ(0,b 1)=θ(a 1,1)=θ(0,b n )=θ(a m ,1),所以Con L 艿(Con L 1×Con L 2)茌軘{,θ(0,a m ),θ(0,b n ),θ(a 1,a m )∨θ(b 1,b n )},其中表示L 的泛同余关系.因为L =m +n +

2,且Con L 1艿2m -1,Con L 2艿2n -1,所以Con L 艿2L -4茌軘22.证毕.称格L 的一个子格I 为理想,若x ≤a ∈I 蕴涵x ∈I ,记θ(I )为由I 所生成的最小同余.记Ω(L )={θ(I )I 是L

的理想}.有如下结果.

定理6若L 是2阶正则图格,则Ω(L )艿22.证明

因为L 是2阶正则图格,所以由定理4可知L 是如图3所示的一个圈.于

是L 的理想I 有4种可能:1)若I ={0},则θ(I )=ω(相等关系);

2)若I =a i ↓,1≤i ≤m ,则θ(I )=θ(0,a i )=θ(b 1,1)=θ(0,a m );

3)若I =b i ↓,1≤i ≤n ,则θ(I )=θ(0,b i )=θ(a 1,1)=θ(0,b n );

4)若I =L ,则θ(I )=.

于是Ω(L )只有4个元素,且θ(0,a m )θ(0,b n )(意指不可比较).因此可知,Ω(L )是一个2阶布尔格.从而Ω(L )艿22.证毕.

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

定理73阶布尔格是最小的3阶正则图格.汕头大学学报(自然科学版)第25卷14

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

参考文献:

[1]Wes t D B.图论导引[M].

李建中,骆吉洲,译.北京:机械工业出版社,2006.[2]Jipsen P ,Rose H.Varie t ies of la tt ices [M]//Lec t ure No t es in Ma t hema t ics.Berlin :Springer Verlag

Press ,1992.[3]

Bly t h T S ,Varle t J C.Ockham algebras [M].Oxford :Oxford Universi t y Press ,1994.[4]

Davey B A.On the lattice of subvarie t ies[J].Hous t on J Ma t h ,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 -ju 1,FANG Jie 2

(1.Department of Mathematics,Shantou University ,Shantou 515063,Guangdong ,China;

2.School of Computer Science,Guangdong Polytechnic Normal University,Guangzhou 510665,Guangdong ,China )Abstract :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 Boolean lattice.All the 1-degree graph lattices and 2-degree graph lattices are found.It is shown that the 8-element Boolean lattice is the smallest 3-degree regular graph lattice.

Key words :regular graph ;lattice ;Boolean lattice 1y b c 0a x z 图5最小的3阶正则图格图4可分解和不可分解的3阶正则图格10L 2L 101孙中举等:具有正则图的有限格的一些注记第2期15