The dimension of the rectangular product of lattices

THE DIMENSION OF

THE RECTANGULAR PRODUCT OF LATTICES

DEOK RAK BAE

ABSTRACT. Inthis paper, we determine the dimension of the rect- angular product of certain finite lattices. In fact, if L1 and ~

be finite lattices which satisfy the some conditions, then we have dim(L1DL2) = dim(L1)+dim(~)- 1.

1. Introduction

We define an ordered set P to be a pair (P, R), where P isa nonempty set and R is an order-relation on P. An order R on a set is called an extension of another order S on the same set if S ~ R. For a, b E P, we usually write a S bfor (a,b) E R and also a < bwhen a S band a 1=b. For elements a> bin an ordered set P, we write a ~ bor b~ a (a cavers bor b is covered by a) ifa ~ c > bimplies a = c for every element c of P. A linear extension of an ordered set P is a linear order E : Xl -< ^X2 -< ... -< ^Xn containing the order of P. E. Szpilarjn [10]

shows that any order has a linear extension. It then follows that the intersection ofall linear extensions of a partial order is the partial order itself. B. Dushnik and E. Miller [3J later defined the dimension of an ordered set P, denoted by dim(P), to be the minimum cardinality of a family of its linear extensions whose intersection is the order itself.

The following alternative definition is often credited to O. Ore [7], but appeared earlier in Hiraguchi [4]: The dimension of an ordered set Pis the minimum size of a family of chains whose direct product embedded P. From this we can easily.see that, for P and Q be arbitrary finite

Received July19, 1997.

1991Mathematics Subject Classification: 06A07.

Key words and phrases: order-dimension, rectangular product, Ferrers relation, Ferrers-dimension, join-cover.

16

ordered sets,

DeokRakBae

max{dim(P),dim(Q)} ~dim(P x Q) ~ dim(P)+dim(Q).

Then we know that the dimension of the product turns out to be always close to the upper bound. W. T. Trotter [11] obtained the following nontrivial result: For positive integersn ~3, then

dim(Sn x Sn) = 2n - 2,

whereSn isthe so-called n-dimensional standard ordered set. C. Lin [6]

obtained the following nontrivial result: For positive integers m, n ~ 3, then

dim(Sm ^x Sn) =m + n - 2.

A lattice is called bounded if it has both the least element 0and the greatest element1. M. K. Bennett [2] defined the rectangular product of two bounded lattices L1 and L2 , denoted by L10L2 , to be the set

{(x,y) I(x,Y) ELl ^X L2with x 1=0and Y1= O}U{(O, On with the order induced from the direct product L₁x L2 , which is also a bounded lattice.

Let J (L) be the set of all join-irreducible elements of the finite lattice L(a E J(L) iff a = VS implies a E S). The set M(L) of all meet- irreducible elements is defined dually. An atom is any element which covers the least element and a dual atomisany element whichiscovered by the greatest element. Let us denote by A(L) and DA(L) the sets of all atoms and dual atoms ofL, respectively. We shall compute the dimension of the rectangular product of the certain finite lattices. To do this we need a concept introduced byR. Wille [12]. LetGand M be the sets and let I be a binary relation between G and M. We defined a context as a triple (G, M,I) and we define a concept of the context (G, M,1),which isa pair (A, B) with the following properties:

A _~ G, B _~ M, A'=B and A =_{B '}

whereA' = {m E M IgImVg E A} and B ' = {g E G IgImVm E B}.

Put

B(G,M,I) ={(A,B) IA c G,B c M}

with the order relation in B(G, M, I) as follows:

(AI, B1 ) ~ (A2 ,B2 ) {::} Al ~ A2 •

Then (B(G,M,I),~) is a complete lattice, which is called the concept lattice of (G,M,!). A relation F ~ G x M is called a Ferrers relation if 91Fm1 and 92Fm2 implies 91Fm2 or92Fm1 for all 91> 92 E G and ml, m2 E M. The Ferrers dimension of a context (G, M,I), denoted by fdim(G,M, 1), is defined to be the smallest number of Ferrers· relations F 1, F2 , ••• ,F_n with1= nFi. Observe that the complement of a Ferrers relation F is again a Fetrers relationin G x M - 1. Therefore, one can alternatively define fdim(G, M,!) as the minimum number of Ferrers relationsF 1, F2 , ••• ,F_nwithFi ~ GxM - 1such thatGxM - 1 = UFi.

Let L be arbitrary finite lattice. Then it is known that (L,L,~) and (J(L), M(L),~J(L)xM(L» are contexts and that

dim(L) =fdim(L,L,~) = fdim(J(L) , M(L),~J(L)xM(L».

We assume throughout in this paper as follows: F is a Ferrers relation in J (L) xM(L) is the same meaning as F is a Ferrers relation in J (L)x M(L) - 1for any lattice L.

Our main result in this paper is the following.

THEOREM. Let L₁ and L₂ be finite lattices with dim(L1 ) = s and dim(L2 ) = t. Suppose that there are Ferrers relations Fi(1 ~ i ~ s) and Gj(1 ~ ^j ~ t) such that U:=l Fi = J(Ll ) X M(L1) - 11 and U~=l Gj =

J(L2 ) X M(L2 ) - h IfJ(Li) = A(Li), M(Li) = DA(Li)(i = 1,2) and

U:=lc(Fi) = J(L1 ) orU~=l c(G^{j ) =} J(L2 ), then we have dim(L10L2 ) =dim(Ld+dim(L2 ) - 1.

2. Preliminaries

To prove the main theorem we need the following lemmas.

LEMMA 1. Let L₁ and L₂ be finite lattices with J(Li)⁼ A(Li) and M(Li)⁼ DA(Li) for ^{i =} 1,2. Then we have

J(L₁0L2) = A(L10L2 ) = A(L₁₎x A(L_2),

M(L₁0L₂₎=DA(L₁0L2 ) =DA(L₁₎ x {1} U {1} x DA(L_2).

An incomparable pair (a,b) in an ordered set P is called a critical pair if x < a implies x < b and x > b implies x > a, then Crit(P) denotes the set of all critical pairs in P and Crit(y) denotes the set

18 DeokRakBae

of all elements x E P with (x, y) E Crit(P). For A ~ P, let AlL =

{x E P I ^{(''Va E A) a} ~ x}, Al = {x E P I ^{(\:fa E A) a} 2: x} and DM(P) ={A ~ P IA^ul =A}. Then (DM(P),~)is a complete lattice, known as the Dedekind-MacNeille completionofP.

LEMMA 2. For any two elements a and b ofa finite lattice L, (a, b) isa critical pairofL ifand onlyifaI\.b isa unique dual coverofa and aVb is a unique coverofb.

Proof Let (a, b) be a critical pair of a lattice L. Ifx < ^{a in L,} then x <bin L and so x < aI\.binL. Hence aI\.bis a unique dual cover of a inL. By duality, there isa unique elementaV bin L such that aVb is covers bin L. Conversely, ifx < ain L, then x < aI\.bin L and so x <aI\.b< bin L. Ify > binL, then y > a Vb> ain L. Hence y >a in L. Thus (a,b) is a critical pair of L. .0

A family 'R = {El, E_{2 , • ••} ,Et} of linear extensions of an ordered set (P,~) is called a realizer of P (also, we say that 'R realizes P) if (P, ~) =_n~=1Ei •

LEMMA 3. [8] Let P be an ordered set and let'R be the family of linear extensionsofP. Then the following statements are equivalent:

(1) 'Risa realizerofP.

(2) For all critical pair (x,y) ofP, thereis a linear extension E E 'R such that y <x inE.

By Lemma2, for any finite latticeL,we haveCrit(L) ~ J(L) xM(L).

In particular, for any two finite complemented modular lattices L₁and L_{2 ,} itisknown that

J(L_{i )} =A(Li ) and M(L_{i )} = DA(L_{i )} and hence we have the following properties:

Crit(L_{i )} = J(L_{i )} x M(L_{i )}nI(L_{i ),}

whereI(L_{i )} is the set of all incomparable pairs inL_i for i = 1,2. Now, by Lemma 1 and Lemma 2, we have the following lemma.

LEMMA 4. Let L₁ and L₂ be finite lattices with J(Li ) = A(L_{i )} and M(L_{i )} = DA(L_{i )} for alli = 1,2. Then wehave

Crit(L₁DL_{2 )} = {((a, c), (b,1)) I^{(a, b) E} Crit (L_{1 )} and cE A(L_{2 )}}U {((a, c),(1,d)) I^{a E A(Lt}} and (c, d) E Crit (L2 )}.

By Lemma 4, we have

Crit(b, 1) =Crit(b) x A(~) and Crit(l,d) = A(LI ) x Crit(d).

Furthermore, we have

Crit(b, 1)n Crit(l,d) = Crit(b) xCrit(d).

For any two subordered setsAand B of the finite latticeL, we define A < B if ^a < bfor all ^{a E} A and b ^E B. Suppose that J(L) =

{abtv.!,'" ,an} and M(L) = {bbb-.2,'" ,bk }. For each Ferrers relation F, in J(L) x M(L), we defined the setsc(Fi), C(F,), r(F,) ^and R(F,) as follows: c(F,) is the set of first coordinate of the shortest column ofFi, C(Fi)is the set of first coordinate of the longest column ofFi, r(F,) is the set of second coordinate of the shortest row of F, and R(Fi) is the set of second coordinate of the longest row ofF_{i .} In fact, there are finite sequences{ainJ inJ(L) and {bileJ in M (L) such that

F,(aid ;2 Fi(aiZ) ;2 ;2 Fi(ainJ (#0) and F,(bil ) ;2 F,(biz ) ^;2 :2Fi(bik;) (#0)

whereF,(a) ={b I(a, b) E F,} andF,(b) ={a I(a, b) E Fi}. In this case, we have

For any Ferrers relation F, in J(L) x M(L) with F,(bil ):2 _{Fi(biZ )}:2

... :2 Fi (bik;), we have a partial linear extensionEi^from Fi asfollowing:

Ei : {bill < ~; <{biZ } <~; < ... < {bi(k;-l)} < ~(k;-l) < {bik;} < F,k;, where ~: = F,(biu ) - Fi(bi(u-I)) ^{for all u} = 1,2"" ,ki - 1, that is, a Ferrers relation of ordered set induces a partial linear extension of the ordered set. If {FI ,Fz, ... ^,Fs } is a family of Ferrers relations in J(L) x M(L) with UFEJ'F= J(L) x M(L) - I, then every critical pair ofL is reversed in UEiEnEi' that is, 'R, = {E1,Ez,'" ,Es } is a realizer ofL. Further, the Ferrers relations are need not disjoint.

We say that the Ferrers relation F is a saturated in J(L) x M(L) if there is no Ferrers relationF' inJ(L ) x M (L) such that F c F'. LetF be a family of Ferrers relations in J(L) x M(L) and let &be a subfamily of F. We say that&is a join-cover (resp, meet-cover) ifUE_E£c(E) =J(L) (resp, UE_E£r(E) = M(L)).

20 DeokRakBae

LEMMA 5. Let L be a finite lattice with dim(L) = s and let F = {F_{l ,}F_{2 , • ••} ,Fs } be a family of Ferrers relations in J (L) x M (L) such thatU:=lFi = J(L) x M(L) - /. Then we have following properties:

(1) IfU:=lc(Fi) = J(L), then c(Fi) and c(Fj) are distinct subsets in J(L) forall i,j withi =1=j.

(2) IfU:=lr(Fi) = M(L), then r(Fi) and r(Fj) are distinct subsetsin M(L) for alli,j withi ⁼¹⁼j.

Proof (1) Suppose not, that is,c(Fi )=c(Fio ) for some^j andjowith j =1= jo· Since U:=lc(Fi) = J(L), it follows that U:=lc(Fi) - c(Fjo) =

J(L). For all 1~i ~ 8 withi ⁼¹⁼jo, let

Ei = Fi U((a,b)E Fio IaE c(Fi)}.

Hence eachE_i is a saturated Ferrers relation inJ(L) x M(L) and Fio' ^~

U:=l,i;FioEi and hence £ = {Et,~,.·· ,Es } - {Eio } ^is the family of Ferrers relations withUE_E^£E =J(L) xM(L) - I and 1£1 ~8-1, which is a contradictionas dim(L) = s.

(2) Symmetrically, we obtain from (1). 0

LEMMA 6. Let L be a finite lattice with dim(L) = s and let F =

{Fl,F2 ,'" ,Fs } be a family of Ferrers relations in J(L) x M(L) such thatU:=l^Fi =J(L) x M(L)-I. Ifthereisasubfamily £ ofF such that UEE£c(E) =J(L) or UEE£r(E) =M(L), then I^FI = 1£1.

Proof Let £ be the subfamily of F with UEE£c(E) = J(L) and let Fo^EF - e^withFo⁼¹⁼0. For allE E e, ^let

E* =E U {(a,b) E FoIaE c(En.

Since c(E) x r(E) is a rectangular Ferrers relation in J(L) x M(L) and UE_E^£c(E) = J(L), it follows that E* is also a Ferrers relation in J(L) x M(L) and Foc UEE£E*. Hence we have

U ^{F U} U^{E* =J(L) x M(L) - /}

FEF-(£u{Fo}} EE£

and I(F - (£U{F_o}»U{E* lEE e}1 = IFI - 1, which is a contra-

diction. 0

LEMMA 7. Let L be a finite lattice. If there are disjoint families

F1 ,F2 ,'" ,Fw ofFerrersrelations in J(L)xM(L) such thatUFEJ'ic(F) =

J(L)(i =1,2"" ,w) with F = U~=~~, then we have the followings:

(1) UFEFF = J(L) ^X M(L) - I implies that dim(L) ~ IFI-w+1 (2) [J(L)xM(L)-I]-UFEFF-I=0impliesthatdim(L) ~ IFI-w+k,

where k =dim([J(L) x M(L) - I] - UFEF F).

Proof (1) Note that l.ril ~ 2 for alli = 1,2,··· ,w. Now we construct new Ferrers relations from F as follows:

:F; ⁼ {F; IF2 E F2 } with F; = F2U{(a,b) E F1 IaE c(F2 )}

:F3 = {F; IF3 E F3 } withF; = F₃U((a, b) E E; Ia E c(F3 )}

.r:v ={F: IFwE Fw } with_F~ = FwU((a,b) E E:a-l IaE c(Fw )}

w-l

:F* = (F1 - {Fl }) U U(F; - {Ea) u.r:v

i=2

for someF1E F1 and Ei E _~* (i = 2,3,··· ,w - 1). ThenF* is the·set of Ferrers relations in J(L) x M(L) and UFEF'F = J(L) x M(L) - I withIPI= IFI-w+1.Hence we conclude that dim(L) ~ IFI-w+1.

(2) Suppose that [J(L) x M(L) - I] - UFEFF -1= 0. Then there is a Ferrers relationFoⁱⁿ [J(L) x M(L) - IJ - UFEFFwithFoi=0. Now we construct Ferrers relations fromF as follows:

.r; = {F; IFl E F1 } with F; = F1U((a,b) E FoIaE c(F1 )}

:F; = ^{F; I^F2 E F2 } withF; = F2U((a,b) E Ei IaE c(F2 )}

.r;, ⁼ {F; ¹F3 E F3 } withF; = F₃U((a, b) E E; ^IaE c(F3 )}

.r:v^{= {F~} IFw E Fw } withF~ = Fw U((a, b) EE:a_l IaE c(Fw )}

w-l

:F* = U (F; - {Ea) u.r:v

i=1

for some Ei E ~* (i = 1,2,··· , w - 1). Then F* is the set of Ferrers relations in J(L) x M(L) and UFEF'F = UFEFFU{Fo}^with IF*I =

IFI - w. Hence we conclude that dim(L) ~ IFI - w +k, where k =

dim([J(L) x M(L) - I] - U~EFF). 0

REMARK. By Lemma 7, we know that if [J(L) x M(L) - I] - UFEFF-1= 0,then we obtains thatdim([J(L) x M(L) - I] - UFEFF) ~

dim(L)-IFI+w. In particular,if [J(L) xM(L) - I] -UFEFF-1= 0and

IFI ~dim(L), then we havedim([J(L) x M(L) - I] - UFEFF) ~w.

22 Deok RakBae

Consider the finite lattices L₁ and L₂ with dim (Ld = s and dim

(~)=t.Then there are Ferrers relationsFI,F_{2 , •.• ,}F_ssuch thatJ(L_{1 )}x M(L_{1) -} 11= _U~=l Fi and there are Ferrers relationsG1 ,G2 ,'" ,Gt such

that J(L2 ) x M(L2 ) - 12 =U~=lGj . For A andC with A c ^J(Ll ) and

Cc J(L_{2 ),} we have the following properties:

dim(J(L_{l )} x C,M(Ll ) x {I},I) dim(J(LlOL2 ),M(Ld x {I},I) dim(J(L1 ),M(L1 ),h)=s dim(J(L₁0L_{2 ),}{I} x M(L_{2 ),}I) dim(J(L_{2 ),}M(~),12 ) = t.

EXAMPLE. Consider the complemented modular lattices L₁ and L2

with L1= ~ = M3 • Then J(M3 ) ={a,b,c} = M(M3 ) and dim(M3 ) =

2. Then there are two Ferrers relations :F = {H,F2 } such that Fl =

{(a,b),(a,c), (b,c)} andF₂ = {(b,a), (c,a), (c,b)}. But we have J(L)-#

c(F_{1 )}Uc(F2 ) ={a, cl. Further, we know that dim(L10~)= dim(Ld+

dim(L2) =4 and so dim(LlOL2 ) -# dim(L1)+dim(L2) - 1.

3. Proof of Theorem

LetL₁andL₂be finite lattices withdim(L_{1 )} =s anddim(~)=t and let:F= {FI,F2 ,'" ,Fs } and g ={Cl,G2 ,'" ,Gt } be the set of Ferrers relations in J(L₁₎ x M(Ld and J(L_{2 )} x M(L_{2 ),} respectively. Without loss of generality, we may assume that U~=lFi = J(L1 ) X M(Ll ) - 11

and U:=lc(F_{i )} = J(Ll ) and that U~=l G^j = J(L2 ) X M(L2) - h For each Fi E:F and Gj Eg, let

Ft = {«(a, c), (b,1))I(a, b) EFi and c E J(L2 )}

G; = {«(a, c),(1,d)) IaEJ(Ll ) and (c,d) EGj }.

Then Fj,* and Gj are Ferrers relations in J(L_lOL_{2 )} x M(L_lDL_{2 ).} In particular, for someG_j Eg, ^let

Uij ={«(a, c),(1,d)) E C; I(a, c) E c(Ft)}·

Then eachFiUUij(i = 1,2,··· ,s) is also a Ferrers relation inJ(L_lDL_{2 ) X} M(LlDL2 ). Since _U~=lc(Fi) = J(Ll ), it follows that Gjo c _U~=l(Fj,* U

Uijo ) for someio with 1:s;io :s;t and hence

s t

U(Fi*^{UUijo ) U} U ^{C; = J(L1DL2 ) x M(L1DL2 ) - I.}

i=1 j=IJho

Hence we have

dim(L1x L_{2 )} :s;dim(L₁₎ +^dim(L2 ) - 1.

Let 1i be a set of the saturated Ferrers relations in J(L₁DL_{2 )} x M(L1DL2 ) with 11i1 :s; dim(L1 ) + dim(L_{2 ) -} 1 = s +t - 1 such that

UHE1lH ^{= J(L}1^{DL2 ) X M(L}1^{DL2 ) -} I and let X ⁼ {H ^E 1i Ir(H) ⁼ B' x {I}} and Y = ^{{H E}1i Ir(H) = {I} x D'} for some B' C M(L1 )

and D' ^C M(L_{2 ).} .

CLAIM 1. X UY is a partition of1i.

Suppose not, that is, there is a Ferrers relation H E 1i such that

{(b,1), (1,d)} ~ r(H). Then

H(b,1) = H(I, d) = {«a, c), (b,1))Ia ~ binL1 and eE J(L2)}n {(a, c), (I,d)) Ia^E J(Lt} in and e ~ din L2 }.

Hence H U {(a, e),(b,1)) Ia _~ bin L₁and e E J(L_{2 )}} is also a Ferrers relation in J(L1^{DL2 ) x M(L}1^{DL2 ) and}{(a, e),(b,1))Ia~ binL1^and e E J(L2 )} et ^H, which is a contradiction. Hence we have X UY is a partition of1i.

Consider the projection mappings 7l"b 7l"2 as follows:

Define 7l"1 : 1i ---+ J(L1 ) X M(L1 ) by

7l"1(H) = ((a,b) I({a} x J(L_{2 ))} x {(b,I)} ~ H}

for H E1i. Similarly, define 7l"2 :1i ^---+ J(L_{2 )} X M(L_{2 )} by 7l"2(H) = {(e,d) I^(J(Lt) x {e}) x {(I,d)} _~ H}

for H E 1i. Let X be an arbitrary element of X. If (aI,bI),(a2' b2) ^E 7l"1(X),thenal ~ b1anda2 ~ b2ⁱⁿLl and «abe),(b_{l ,}1)),«a2'c),(~,1)) E X for all e E J(L2). Hence we know that «abc),(b2,^{1)) E X or}

«a2'e),(bb 1)) E X for all e E J(L2) ^{and hence} (ab~) E 7l"l(X) or (a2'bl ) E 7l"1(X), Thus 7l"1(X) is a Ferrers relation in J(Ll ) x M(L1 )

for all X E X. Similarly, we know that 7l"2(Y) is a Ferrers relation in J(L_{2 )} x M(L_{2 )} for allY E y.

24 DeokRakBae

Define PI : 1£~ J(L l)^X M(L l )^by

Pl(H) =Ha, b) I((a, c), (b,1»^EH}

for H ^E 1£. Similarly, defineP2 : 1£ - - J(L2)^X M(L2)^by P2(H) = {(c', d') I((a',c'),(1,d'» EH}

for H E1£. For X EX, if(ar, bl ),(a2,~)E Pl(X), thenal 1:bl ,a21: ~

in L l and ((al,c),(bb1»,((a2,c'),(~,1»E X for some c,d E J(Lz).

Hence we know that ((aI, c),(~, 1» E X or ((a2, c'), (bl ,1» E X for some c,d E J(L2)^{and hence (ah~) E} Pl(X) or (a2,br) E Pl(X), Thus Pl(X) is a Ferrers relation in J(Ll) x M(Ll) ^{for all}X EX. Similarly, we know that P2(Y) is also a Ferrers relation in J(L2)^x M(L2) ^{for all} Y E y. Hence, for H E 1£, we conclude that 7ri(H) and Pi(H) are saturated Ferrers relation in J(Li)^x M(Li)^{fori = 1,2.}

CLAIM 2. IXI ? ⁸ or IYI ~t.

Suppose that IXI =81 < 8 and IYI=tl < t.

Step 1. For all X E X and Y E Y, we know that PI (X) and P2(Y) are saturated Ferrers relations in J(Ll )^x M(Ll ) ^and J(L2)^x M(L2), 'respectively. Then thereisat least one Ferrers relationUlⁱⁿJ(LlOLz)^X

M(LlOL2)^{such that}

({al} x J(L2))x {(br,1)}CUI - U^Xc U^Y

XEX YEY

for some (ar,br) E J(Lr) x M(Ll ) - ^[1- Similarly, there is at least one Ferrers relation Vi in J(LlDL2) ^X M(LlDL2)^{such that}

(J(Ll ) x {Cl}) x {(l,dl )} C Vi - U^{Y c} U^X

YEY XEX

for some (cr,dl) ^E J(L2) ^x M(L2)-lz. If{7rl(X) IX E X} does not a join-cover of LIar{7r2(Y) lYE Y}does not a join-cover ofL2 ,thenUl rt.

UHEl£H orVi rt. UHEl£H,which is a contradiction. Then we may assume that UXEXC(7rl(X» = J(Ll ) and UX'EX,C(7rl(X'» 1= J(Ll ) and that

UYEY C(7r2(Y» = J(L2)^{for allX'} c X. Since({al}xJ(L2»x{(br,^{1)} C} Ul ^{C UYEY1';}it follows thatdim([J(LlOL2)^{x ({1} x} M(L2»-[] -^{Vi -}

UYEYY) ? 1 by Lemma 7. Hence there is a Ferrers relation V2 in J(L1DL2)^x M(LlOLz)^{such that}

(J(Ll ) x {C2} - c(Ul» x {(1,d2 )} c V2 - Vi - U^Ye U^X

YEY XEX