3-Interval irreducible partially ordered sets

Author: Felsner S.

19 downloads 687 Views 2MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Order 11: 97-125, 1994. © 1994 KluwerAcademic Publishers. Printed in the Netherlands.

97

3-Interval Irreducible Partially Ordered Sets* STEFAN

FELSNER

Freie Universitiit Berlin, Fachbereich Mathematik, lnstitut fiir Informatik, Takustr. 9, 14195 Berlin, Germany (E-mail: [email protected]) Communicated by W. I:. Trotter (Received: 6 March i993; accepted: 20 May 1994) Abstract. In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posers for interval dimension 2. Members of this list are called 3-interval irreducible posers. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posers) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posers due to Trotter [9]. We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posers. Our arguments depend on a transformation P ---, B ( P ) , such that I d i m P = dim B(P). This transformation has been introduced in [2]. Mathematics Subject Classifications (1991). 06A07, 05C35. Key words. Partially ordered sets, interval orders, dimension.

1. I n t r o d u c t i o n

and Basics

An extension of a poset P = (X, < p ) is a partial order Q = (X,
98

STEFAN FELSNER

P iff bx < a v in C. Fishburn [3] characterized interval orders as the posets with no 4-point subset forming two disjoint 2-chains, i.e., no 2 + 2. The interval dimension of P, denoted Idim(P), is the smallest k for which there exist k interval extensions of P which realize P. Since linear orders are interval orders we obtain the trivial inequality Idim(P) ~< dim(P). If pt = (X ~,<) is a suborder of P = (X,<), then dim(P') ~< dim(P) and Idim(P ~) ~< Idim(P). Therefore, for every integer k there is a minimal list of posets of dimension (interval dimension) k + 1, such that every poser which does not contain a subposet from this list has dimension (interval dimension) at most k. Members of this list are then called (k + t)-irreducible ((k + 1)-interval irreducible) posets. Note that a (k + 1)-irreducible ((k + 1)-interval irreducible) poset P has dim(P) = k + l(Idim(P) = k + 1) but the removal of any element lowers its dimension (interval dimension). The list of 2-irreducible posets contains only the 2-element antichain and the list of 2-interval irreducible posets contains only 2 + 2. The list of 3-irreducible posets is of a much higher complexity. Counting only one of P and pd, the dual of P, the list consists of 10 isolated examples together with 7 infinite families (see Figure 1). This list has been obtained independently by Trotter and Moore [8] and by Kelly [4]. Since this paper depends on the ideas of Kelly's argument we now give a brief (and in some details not even correct) outline of his proof. Let L(P) denote the completion by cuts of a poset P, i.e., L(P) is the smallest lattice containing P as a suborder. Kelly's characterization of the 3-irreducible posets is mainly based on two results: (1) dim P = dim L(P). (A theorem of Baker.) (2) The complete list £ of lattices of dimension 3 with the property that every proper sublattice is of lower dimension. (Let us remark that a lattice is planar exactly if it contains no sublattice from 12.) The list £ had been obtained by Kelly and Rival [5]. Suppose that P is a 3-irreducible poser. It follows that dim L(P) /> 3, therefore, L(P) contains one or more of the lattices in/2 as sublattices. The key idea for the proof is to consider the lattices in/2 in a specific ordering, the Kelly order. At an intermediate step in the argument we assume that L(P) contains a lattice Q from this list, but does not contain any lattice preceding it in the Kelly order. The details of each individual case center around chosing a copy of a 3-irreducible subposet R of Q and then one by one showing how those points of R which do not belong to P can be replaced by points of P. A poser P = (X, <) is called bipartite if there are two sets X1, )(2 C_X, such that z < y implies z E X1 and y E X2. Trotter found a transformation, which associates with a bipartite poset P a poser Stack(P), such that, Idim(P) = dim Stack(P). This fact, together with the existing list of 3-irreducible posers lead to the characterization of bipartite 3-interval irreducible posets in [9].

3-INTERVAL IRREDUCIBLE PARTIALLY ORDERED SETS

99

CLb~ B

C

~

D

CX2

~

C2

~e

~

b~

CXx bz ~c

b3

a3 0,3

b2 EX1 ~3

a3

b~ FXI

•

FX2

represents/-labeled elements represents elements that are l- and u-labeled represents u-labeled dements

Fig. 1. ~l~e 3-irreducible orders (part 1).

b3 EX2

b3

100

STEFAN FELSNER

e

~

'

D

'

+

lqp'~l,n+ 2

F,,

d

e

d+

e

d+

I.

bn+a

~a I Fig. 1. The 3-irreducible orders (part 2).

~ a2

f~az -"- IIF---

~
3-1NTERVALIRREDUCIBLEPARTIALLYORDEREDSETS

Gn~

101

bn+z t bn+2

c

bn+l bn

D, "

an+3

•

atn+'~

G4i

¢1n+1

(13

d ;

b.

(13

d

b2

a ¢

a2

al

b~,

c

a2

tl1 Fig. 1. The 3-irreducible orders (part 3). Trotter's proof uses Kelly's approach for the characterization of the 3-irreducible posers as a road map. Since the stack of a bipartite 3-interval irreducible poset P contains one (or more) of the 3-irreducible posers we can argue about the implications for the original poser. Again, a specific ordering of the 3-irreducible posers and corresponding assumptions about the 3-irreducible posers contained in Stack(P) are

102

STEFAN FELSNER

critical elements of the proof. In [2] we have introduced a transformation P ~ B(P), such that I d i m P = dim B(P) for arbitrary posets P. In this paper we use this operator P --. B(P), to approach the characterization of 3-interval irreducible posets. The argument is again based on a Kelly ordering of the 3-irreducible posets. Let P = (X, <) be a poset. For x E X we denote the predecessor set {y E X: V < x) of x with Pred(z), the successor set {y E X: V > z} is denote by Succ(a~). The closed predecessor set is Pred[x] = {y E X: V ~< x}, i.e., Pred[z] = Pred(z) t.J {x), similarly, Succ[z] = Succ(x)U{a:}. We now review the definition and some properties of the transformation P --~ B(P). DEFINITION 1. For each element x of a poset P = (X, <) let L(x) = Pred(x), U(x)=

N Vred(z), ze Succ(x)

if Succ(z) = O then let U(z) = X. With P we associate a poset B(P) = (Y, <). The elements of Y are the distinct sets occurring as L(z) or U(x) for some x E X. The ordering of B(P) is given by set-inclusion. The next defnition is taken from [7]. DEFINITION 2. For posets P = (X, < p ) and Q = (Y,
3-INTERVALIRREDUCIBLEPARTIALLYORDERED SETS

103

(2) The dimension o r B ( P ) equals the interval dimension of P. We now come to the stack of a bipartite poser. As mentioned above, the stack played a central role in the characterization of bipartite 3-interval irreducible posets. DEFINITION 3. Let P = (X, < p ) be a (connected) bipartite poset and let O be an arbitrary linear order on X. Let A denote the set of minimal elements and B the set of maximal elements of P (we assume that a, ai E A and b, bl E B). The Stack(P) is an extension of P, whose relations are given by a
ifa
bl < b2

if eredp(bl) C eredp(b2),

al < a2

if Succp(al) 2 Succp(a2),

b
if a ][ b and a' < b' in P for all a' E Predp(b) and b' E Succp(a),

bl < b2 if Predp(bl) = Predp(b2) and bl < o b2, al < a2

if Succv(al) = Succp(a2) and al < o a2.

We now show, that for a bipartite order P the posets B(P) and Stack(P) are intimately related. Let the 0, 1-closure of P, i.e., the adjoin of a least element 0 and a greatest element 1, be denoted by P ~ / 3 . THEOREM 2. I f P = (X, <) is a bipartite order, then B(P) = Stack(P)l~ , here ,~ is an equivalence relation on X with the properties: • each class of ~ is an autonomous subset of Stack(P), ® Stack(P) induces a chain on each class o f ~ . Proof. An element x E X is mapped to two elements of B(P). Since P is bipartite we either have L(z) = O or U(x) = X. In the first case let M(z) = U(z); in the second case let M(z) = L@). Also, let O be the linear order used in the construction of Stack(P). Define a poser Q on X by (1) z
104

STEFAN FELSNER

a < b in P: In Stack(P) we have a < b by definition. Note that

M(a) = V(a)=

~ Pred(b') b' e Suce(a)

and

M(b) = Pred(b).

Since a < b we find Pred(b) in the intersection defining M(a). Hence, M(a) C_ M(b) and a
Proof This is an immediate consequence of the next theorem.

[]

THEOREM 3. Let P = (X, 1 y2 but L(x) ~ Yl.

Proof The equivalence of (1) and (2) is an easy consequ.ence of the following: y = {x E X: U(x) C y}

for all e l e m e n t s y o f B ( P ) .

3-INTERVALIRREDUCIBLE PARTIALLYORDERED SETS

105

First, suppose that y = L(xo) for some x0 E X. If x E y, i.e., x E L(xo) = Pred(x0), then x < x0. From x0 E Succ(x) it follows, that

U(x) =

A

Pred(x') C_ Pred(xo) = y.

x' e Suex(:~) Conversely, let U(x) C y. From x E U(x) we obtain x E y. Now suppose that y = U(zo) for some x0 E X. If x E y, i.e.,

x E U(xo)=

A Pred(x'), x' ~Suec(~o)

then x < x' for all x' > x0. Therefore, Succ(x) __. Succ(x0) and hence U(x) CC_ U(xo) = y. Conversely, let U(x) C_y. From x E U(x) we again obtain x E y. The equivalence of (1) and (3) is obtained by duality. The argument is based on the following observation: There is an isomorphism between B(P a) and B(P) d, such that, the interval representation of pd on B(P) a is obtained from the interval representation of P on B(P) by interchanging L and U. [] REMARK.

Let an interval representation L, U: P ~ Q of P on Q be called a

proper interval representation if for all Yl, Y2 E Ira(L) to Ira(U) the 3 statements of Theorem 3 are equivalent. If L, U: P --+ Q is a proper interval representation, then the ordering of Q restricted to Im(L) tOhn(U) is isomorphic to B(P) and the interval representations of P on the restriction of Q and on B(P) are equal with respect to this isomorphism. Hence, B(P) can be characterized as the unique minimal poset which admits a proper interval representation of P. 1.1. BIPARTITE3-INTERVAL IRREDUCIBLE ORDERS We are ready to show, how the list of bipartite 3-interval irreducible orders given in [9], see also [8], can be predicted. Although this list is known for more than 15 years, we propose that our method is new and interesting. We stag by introducing some notation. DEFINITION 4. Let P = (X, < p ) be a poset and B(P) = (Y, <). Aa~ element y E Y is called low-made if y = L(z) for some z E X; it is called up-made if y = U(x) for some x E X. Let Q = ( Y , < ) b e a p o s e t . Label an element y E Y with £ if there is a y' E Y such that y II y', i.e., y and y' are incomparable, and Succ(y) C Succ(y'). An element y E Y is labeled with u if there is a y' E Y such that y [I Y' and Pred(y) C_ Pred(y'). This gives the (g, u)-labeling of Q = (Y, <). Note that y E Y is labeled £/u in this labeling, if y is forced, by Lemma 2, to be low-made/up-made, whenever Q = B(P) for some P .

106

STEFAN FELSNER

agu

b~

cIU

au

el

b2u

b~~

Fig. 2. The 3-irreducibleorder C and the bipartiteorder 0 2 correspondingto the (l, u)-labeling of C. Now suppose, that Q = (Y, <) is 3-irreducible. Recall that a critical pair is a incomparable pair (Vl, Yz) with Pred(yl) D Pred(y2) and Succ(vl) C_ Succ(y2). It is easy to see (cf. [6, 10]), that the 3-irreducibility of Q implies that every V E Y is contained in some critical pair. Hence, every element V E Y will receive at least one label in the (t, u)-labeling of Q. (See Figure 1 for the (t, u)-labelings of the 3-irreducible posets.) If every element of a poset Q = (Y, <) has received a label in the (t, u)-labeling, then a minimal bipartite order P with B(P) = ~) is easily obtained: For every ulabeled element V E Y take a minimal element V~' and for every t-labeled element z E Y take a maximal element z t. The relations are given by V~' < zt if and oldy if V <~ z in Q (for an example see Figure 2). If Q is 3-irreducible then, in view of the preceeding remarks, the order P obtained by this process may be considered as a candidate for the list of bipartite 3-interval irreducible posets. To check the irreducibility, we construct B(P,) for every point deleted suborder Px of P and compute dim B(P~). If dim B(P~) = 2 for all z, then P is indeed a 3-interval irreducible poset. The results are given in the list below. Our notation and labeling for the collection of all 3-irreducible orders (see Figure 1) was introduced by Kelly [4], it is also used in [9] and [10]. For bipartite 3-interval irreducible posets we use the notation introduced in [8] (see also [9]). Q = An: Here we obtain the family .An. Q = B: Here we obtain O1. Q = C: Here we obtain O2. Q = D: Here we obtain 270. Q = EX2: Here we obtain 03. Q = CXl: The order P obtained here is not irreducible. Removing by from P we have B(Pb~) is the dual ~a of ~E, i.e., Iditn(Pb~) = 3. Q = CX2: The order P obtained here is not irreducible. Removing by and b~ from P we have B(Pb~,~) = ~¢t. Q = CXa: The order P obtained here is not irreducible. Removing b'~ and a~ from P we have B(Pb, a') = f}. Q = EXI: The order P obtained here is not irreducible. Removing b~ from P we have B(P~) = E0.

3-INTERVAL IRREDUCIBLE PARTIALLY ORDERED SETS

107

Q = FXI: The order P obtained here is not irreducible. Removing a~ from P we have B(Pa~ ) = Fo. Q = I~LK2:The order P obtained here is not irreducible. Removing a~ and by from P we have B(P~,b~) = Fo. Q En: Here we obtain the family 8n. Q = Fn: Here we obtain the family ~,~. Q = In: Here we obtain the family 27~+1. Q = Gn: Here we obtain the family ~n. Q = Hn: Here we obtain the family 7-/n. Q = Jn: The order P obtained here is not irreducible. Removing c~ and d ~ from P we have B(P~qd~ ) = Gn. Let Q = (Y, <) be a 3-irreducible poset and let P be the bipartite order corresponding to the (£, u)-labeling of Q. A label p E {£, u} of an element y E Y is called essential if dim B(Py,) = 2. Note that, P is 3-interval irreducible exactly if every label of Q is essential. Above we have compiled a list of bipartite 3-interval irreducible posets. To prove that this list is indeed complete, i.e., consists of all bipartite 3-interval irreducible posets, however, a large amount of work remains. This work has been accomplished by Trotter [9]. In the next section we give a modified version of his argument to prove our Theorem 4. REMARK. The split of a poser P = (X, <) is the bipartite poset with maximal elements {ze: x E X} and minimal elements {x~': x E X} with z ~ < Vz in Split(P) iff z ~< y in P. Note that, as a consequence of Trotter's result we can state that every bipartite 3-interval irreducible poset is a subposet of the split of some 3-irreducible poser.

2. General 3-Interval Irreducible Posets The program for dealing with the general (non-bipartite) case is the following: In the first part, we use the techniques developed in [9] for the characterization the bipartitie 3-interval irreducible orders to show that every 3-interval irreducible order contains a partial stack or a reduced partial stack of a bipartite 3-interval irreducible order. In the second part, we then attempt to characterize the 3-interval irreducible orders among the candidate posets obtained in the first part. 2.1. PARTIAL STACKS AND REDUCED PARTIAL STACKS

DEFINITION 5. Let P = (X, < p ) be a (connected) bipartite poset with minimal elements X1 and maximal elements X2. Apartial stack of P is an order Q = (X,
108

STEFAN FELSNER

REMARK. Let P = Of, < p ) be a (connected) bipartite poser with minimal elements XI and maximal elements X2. Let Ep be the set of all extensions Q of P satisfying zl < q ~z iff z l

0 for which B ( P ) contains Ak. We will then show that P contains Ae. Of all copies of Ak contained in B(P), choose one for which the integer t = I{b~: 1 ~< i ~< k + 3, b, is low-made)[ + + [{ai: 1 ~< i ~< k + 3 ,

a~ is up-made)l

is as large as possible. If t = 2k + 6, then for 0 ~< i ~< k + 3 there are elements a~, b~ in P with L(b~) = bl and U(a~) = ai. These elements form a copy of Ak in P. Assume that t < 2k + 6 and without loss of generality let bk+z be a non low-made element. Since al II b +2 in B(P), it follows from Theorem 3, that there is an element z E X so that L(a~)/> bk+z and L(z) [t al. If L(x) il ai for each i = 2, 3 , . . . , k + 1, then x can replace bk+z in this copy of Ak. So we must have L(z)/> ai for some i with 2 <~ i ~< k + 1. Let i0 be the smallest such integer. Then it follows that the subposet of B ( P ) generated by {al, a2 . . . . , aio, ak+3) U (bl, be. . . . , b/o_l, L(x), bk+3} is Ai0_z. But i0 - 2 < k, this is a contradiction.

[]

3-INTERVALIRREDUCIBLE PARTIALLYORDERED SETS

109

T H E O R E M 6 (Trotter's Theorem 7). Let P be a poset and suppose that P does not

contain a crown A~ for any n >10. I f y is an up-made (low-made) element of B(P) and F is a connected subposet of Inc(y), then there exists a low-made (up-made) element x in B(P) so that x ) y (y >t x) and F C_ Inc(x). Proof We prove the theorem when y is up-made. If y is also low-made, then x = y and we are done. Suppose that y is not low-made. Let y' > y be low-made and note that the existence of a low-made element y" > y with y" [[ y' is guaranteed by Theorem 3. Therefore, there are at least two incomparable low-made elements in SUCCB(p)(y). If there is a z E F with x ) z for all low-made elements x > y, then y / > z by Theorem 3. A contradiction. We therefore may assume, that there are elements x, x' E SUCCB(p)(y) and z, z' E F such that z < x and z' < x t but x il z' and x' 1[ z. Now let a l , . . . , an be a fence in F from z' to z. It follows that {x, y, x', a l , . . . , an} contains a crown. A contradiction. [] Let P = (X, < p ) be a 3-interval irreducible poset. Since the dimension of B(P) is 3, B(P) contains a 3-irreducible poset. Suppose first, that B(P) contains a crown A,~ for some n ) 0. Then, it follows from Theorem 5, that P also contains a crown A,~ for some o ~< m ~< n. Since P is irreducible, we conclude, that P = A,~. We may, therefore, assume in the remainder of the argument, that B(P) does not contain a crown An. The remainder of the argument is divided into a sequence of cases. When discussing the case of a 3-irreducible order Q = (Y,
SuccB(e)[u"] n Y

= Succo[v 1.

The element yt then is any element with U(y u) = y'q We will make extensive use of the following easy consequence of Theorem 6. L E M M A 3. Let P = (X, < F ) be a crown-flee poset and suppose that a 3-irreducible poset Q = (Y, < Q ) / s contained in B(P). I f y is an element of Q such that IncQ(y) is connected and for all y' in Q with y' f~ PredQ[y] (b/ ¢[ SUCCQ[y]) there is a y" E IncQ(y) with y' >>.y" (g' ~ y"), then there is an element ! / ( y ~ ) in P.

11 0

STEFAN FELSNER

In each case we choose a particular 3-irreducible poset Q = (Y,
Case 1. B(P) contains D. We apply Lemma 3 to obtain elements t,1,/~t,2,/'~~'3' ~g 6~1' C~ and a ~', b~, b~, b~ in P. The bipartite order (X ~' x X l ) n < p forms a copy of 27o in P. Hence, P contains a partial stack of 270.

Case 2. B(P) contains C. t ~ u From Lemma 3 we may assume, that there are elements el, e3, b~ and a u, b~, el, e~. Suppose, that there is no element e~. Then by Theorem 6, there are elements e' > e2 and e" > e2 in B(P) with el E Inc(e") but d' > e3 and e3 E Inc(e') but e' > el. This implies that {a, el, e", b3, d, e3} form a copy of D in B(P). The contradiction allows us to assume an element e~. Assume, that bl is low-made, then choose an up-made element b] < bl with b2, c3 C Inc(b]). If b~ < b3, then {c2, be, a, cl, b], 63) form a copy of D d in B(P). We conclude, that b3 E Inc(b]), hence, any U-preimage of b] is b~. Symmetrically, we may assume an element b~. The bipartite order with maximal elements Cl, ~ c2, ~ c3,~b3 and minimal elements a ~, b~, b'~,b~, c~, c~ forms a copy of O2 in P. Hence, P contains a partial stack of 02.

Case 3. B(P) contains CX3. From Lemma 3 we may assume that there are elements a~, bpb3, ~ ~ c~ and a~,a~,b~. Choose a low-made element b~ > b2 with b3, c E Inc(b~). If b~ > bl, then {a2, bl, b~, a3, e, b3} form a copy of D in B(P). Therefore, we may assume an element b~ in P. If there is no element a~, then there are up-made elements a~ < az and a t < az with a 1 }[ a~ but a~ < a3, and a3 l[ a~ but a~ < a 1. However, it follows, that {b2, al, a~, b3, a~, a3} form a copy of D a. The contradiction shows that we may assume an element a~. The bipartite order corresponding to these elements y~ and y~ as maximals and minimals forms a copy of 270 in P.

Case 4. B(P) contains CX2. From Lemma 3 we obtain elements a~, a~, cz and a~, a u3 ' c" "

3-INTERVAL IRREDUCIBLE PARTIALLYORDERED SETS

111

The same argument used in Case 3 allows us to assume an up-made element a~. Next, choose a low-made element b~/> b3 with {bl, b2, al} E lnc(b~). If b~ > c, then B(P) contains CX3. Therefore, we assume an element b~. By symmetry, we may also assume an element b~. Finally, choose a low-made element b~ > b2 with c E Inc(b~). Obviously, bl ~ b~ and e2 ~ b~. Let :c be a preimage of b~ under L. The bipartite ~ c~ and minimal elements a~, a2,a3,c ~ ~ u order with maximal elements a ~1, a l3, b~1, x ,~'3, forms a copy of O~ in P.

Case 5. B(P) contains CXt. If bl is not low-made, then choose a low-made element b] > bl with {a3, bz, c} _C Inc(b]). If b] > b3, then {a2, b3, hi, al, c, be) form a copy of D. Therefore, we may assume that there is an element b~ in P. If there is not element a~, then there are up-made elements a~ < a2 and a~ < a2 with al 11a~ but a~ < a3, and a3 [1 a~ but a~ < al. It tbllows, that {c, al, a~, b3, a~, a3} form a copy of D a. The contradiction shows, that we may assume an element a~ in P. If b2 is not low-made, then choose a low-made element b~ > bz with al, bl C Inc(b~). If b~ > b3, then {al, az, a3, bl, c, b3, b~z} form a copy of CX3. We, therefore, assume an element b~ hi P. From Lemma 3 we obtain elements a], a~, b~ and a~, a~, b~. We also may choose a low-made element d > c with b3 E Inc(d). Let z be a preimage of d under L. The bipartite order with maximal elements a~, at3, ~l,~lb~, b~, z and minimal elements a~, a~'2,a~3, b~'3 forms a copy of Oza in P.

Case 6. B(P) contains EXz. Suppose, that b2 iS not low-made and there is no low-made element b~ > b2 with e, b3 E lnc(b~). Then it follows that there exist points b4, b5 > bz with b3 E Inc(b4) and e, bl E Inc(bs). This implies that b5 > b3. If b4 > e, then {a2, bl, c, a3, bs, b3} generate a copy of D. So we must have b4 [[ e, and thus b4 > bl. However, this implies that {e, bl, b4, b2, b3, a2, a3} generate a copy of CX1 in B(P). The contradiction allows us to assmne an element b~ in P. Since EX2 = EX~ we obtain a~ from the dual argument. If e is not low-made, then choose an element c I > c with a3, b2 E Inc(d). If d > b3, then {d, b3, a2, bz, al, bl} form a copy of D d. We, therefore, may assume an element cz. Dually, we may assume a~. From Lemma 3 we obtain elements a l3, bl, L b3t and a3, ~, bu1, b3. ~, The bipartite order t bl, ~ b~, b~, ce and minimal elements a~, a~, a~, by forms a with maximal elements a3, copy of O3 in P .

Case 7. B(P) contains FX1. If b2 is not low-made, then choose a low-made element b~ > b2 with b~ I1 b3. If b~ > bl, then B(P) contains D. Hence, we assume an element b~ in P.

112

s TEFAN FELSNER

If there is no element a~, then there are up-made elements a] < al and a I!i < al with a2, b3 E Inc(a]) but a] < a3, and a3 E Inc(a~) but a~ < b3. It follows, that {c, b3, a~~, bl, a], a3} form a copy of D d. The contradiction shows, that we may assume an element a~ in P. If there is no element a~, then there are up-made elements a~ < a2 and a~ < a2 with ai 11a~ but a~ < az and a3 ]l a~ but a~ < ai. It follows that {b2, al, a~, b3, a~, a3} form a copy of D a. The contradiction shows that we may assume an element a~. From Lemma 3 we obtain low-made elements a3,t bi,t b~, e~ and up-made elements a3,u bl,u b3.u The bipartite order with maximal elements a3,t bl,l b~, b~3,cl and minimal elements ai, a2, a~, by, b~ forms a copy of ~'0 in P.

Case 8. B(P) contains EX1. Choose a low-made element b[ > b2 with a3, b3 E Inc(b~). If b~ > bl and b[ > b4, then {hi, hi, ax, b3, a2, b4} generate D d. If b[ > bl and b[ 1[ b4, then replacing b2 by b[ we obtain EX2. If b[ > b4 and b~ [1 bi, then the same elements also generate EX2. Hence, we may assume an element b~ in P. Choose a low-made element b~ > b3, such that b2 E Inc(b~). If b~ > hi, then {ai, a2, a3, ba, b2, b3, b~} forms a copy of FX1 in B(P). If b~ > b4, then {al, a2, a3, b2, b3, b~, b4} generates FXI. We may, therefore, assume that there is an element b~ in P. If there is no element a~, then choose an up-made element a t < al with a2, b4 E Inc(a]). If a] < a3, then B(P) contains a copy of FX~. Thus, we may assume a3 I[ at, i.e., we may assume an element a~ in P. By symmetry, we may also assume an element a~ in P. From Lemma 3 we obtain elements a3, bl, b~ and a~, b~, b~. The bipartite order (X ~' × XZ)n < v is a copy of go in P.

Case 9. B(P) contains FX2. If there is no low-made element d > c with bi, b3 E Inc(d), then choose Cl > c and c2 > c with b3 [[ el but bi < % and bl [[ c2 but b3 < c2. It follows, that B(P) contains a copy of D. We, therefore, may assume an element cl. Dually, we also assume an element a~ in P. Now, choose a low-made element b~ ~> b3 with c, b2 E Inc(b~). If b~ > bi, then B(P) contains D. We, therefore, assume an element b~ in P. Dually, we also assume an element a~. From Lemma 3 we may assume elements a3, b l , l~ b~ and a3,bi,b It '~ ~' 2 in P. The bipartite order generated by these elements is a copy of 5% h / P . In cases 10 to 13, the next lemma will find repeated applications.

3-INTERVALIRREDUCIBLEPARTIALLYORDERED SETS

113

L E M M A 4. Let P be a poset such that B ( P ) contains no D, CX3, nor their duals

nor a crown An. Let aa, bb az, bz, a3,...,an, bn be a fence in B ( P ) and x > bi for some i E { 1 , . . . , n } . (1) I f j l is the minimal, J2 the maximal integer with z > ai~ and z > aj2 , then

z > aj when j l <~j <~j2. (2) 1f j l is the minimal, J2 the maximal integer with x > bit and x > bj2 , then x > bj w h e n j l <~j <~J2. Proof If z II aj for some Jl ~< J ~< J2, then B ( P ) contains a crown. If z tl bj but x > bj-1 and x > bj+l, then B ( P ) contains D d. Finally, suppose that z > bj. and x > bj. and j . + 2 < j* but x If bj for all j . < j < j*. Then from the first part we know that z > a j . + l , a j . + 2 and the elements of {aj., aj,+l, aj.+2, bj., bjo+l, bjo+2, x} generate a copy of CX3 in B(P). [] Note that the dual o f this lemma is also true, i.e., if z is below some element ai, then the elements of the fence comparable with x are intervals of a's and b's.

Case 10. B ( P ) contains Fn. We also assume that B ( P ) does not contain Fro, Era or Edm when 0 ~< m < n. Now suppose, that 2 ~1 bi and

Hd. Suppose, that z < e, it follows that x 11bl. Let Jl be the minimal, J2 the maximal integer with z > ajl and x > aj2. If J2 = j l + 1, then there is an element b~ in P. Otherwise, { a l , . . . , a j ~ , a j 2 , . . . ,an+e} U {bl,...,bj~,x, bj2+l . . . . ,bn+2} U {c,d,e} generate Fra for some m < n. Now suppose, that z II e. If z II a +2 then

{aj2,... ,an+2} U {x, bj2+l,... ,bn+2} U {c, d,e}. generates Fra for some m < n. We, henceforth, may assume that x > an+2. If z > bi, then {e, d, e, am+z, z, bl} form a copy of D. Now assume, that z II bl and Jl > 1, then

{al,...,aj~} U {bl,...,bj~,z} U {d,e} generate Era for some m < n. Finally, if bl, e E Inc(z) and x > al, x > an+2, then {al, a,~+2, bl, c, d, e, z} form a copy of F X d. We may, therefore, assume an element b~ in P . By symmetry and duality we may also assume elements a.~ when l <~ i ~< n + 1. From Lemma 3 we obtain a,~+2,l b~l,el, d ~ and a~+2, by, c u, d u in P. The bipartite order corresponding to these elements forms a copy of ~'n in P.

114

STEFAN FELSNER

Case 11. B ( P ) contains E , . We also assume that B ( P ) does not contain F,~, Em or Ea~ when 0 ~ m < n. Now suppose, that 1 ~ 1 then { a j o - b ajo,.. ., at+l} L.J {b/o , b j o + l , . . . , bi+l) k.J {a t ,c) forms a copy of E~m where m < n. If J0 = 1 then {al, a2, . . . , at+l} U {bl, b 2 , . . . , bi+l} U {a', c, d} forms a copy of F d where m < n. The contradiction allows us to conclude a' II c. Let Jl (J2) be the minimal (maximal) index j with a' < bj. If J2 • Jl -4- 1, then {al, . . . , ajl_l, a', ajz+l,..., an+2} LJ { b l , . . . , bjl , bj2,... , bn+3} U {c, d} forms a copy of E ~ where m < n. We may, therefore, assume elements a ~ , . . . , a,~+lu and by symmetry also a~+ 2. Next choose an integer i with 2 ~>,bi with x 1[ c. Suppose, that x II d. Suppose x > al and x > an+2. If bl, bn+3 E Inc(x), a copy of EX1 is generated by {bl, z, bn+3, d, al, an+2, e}. The same point set generates EX2 if only one of bl and b~+3 is incomparable with z. It contains D a if bl, bn+3 < x. We now assume, without loss of generality, that x [I a,~+2. Let Jo be the maximal index j with x > aio, it follows that { a j o , . . . , an+2} U {x, b j 0 + a , . . . , b n + 3 } L.J {c, d} generates Earn where m < n. Now suppose that x < d. Thus bl, bn+3 E Inc(x). Note that if z > aj for some j ~ i - l, i, then B(P) contains Edm for some m < n. £ b3,..., £ l 2 in P. Therefore, we may assume the existence of elements b2, bn+ z c~,d~ and bl, u bn+3, ~ c~. The Finally, from Lemma 3 we obtain elements bl, bn+3, bipartite order corresponding these elements forms a copy of j r in P.

Case 12. B ( P ) contains B. Suppose that a is not up-made. If there is an up-made element a ~ < a with ISucc(a') n {bl, b2, b3}l = 1 then B ( P ) contains Eg. Otherwise, there are up-made elements al, a2, a3 <<,a with at [1 bi and at II aj for i = 1, 2, 3 and j # i. However, {al, a2, a3, bl, b2, b3} generate a crown A3 in this case. We, therefore, may assume an element a u. Next, choose a low-made element c] ~> el with b2, c2 E Inc(c]). If c] > c3, then B ( P ) contains C a. So we assume c] II c3. If > b3, then B ( P ) contains CX1, so we may assume that c] 11b3. This gives an element c~ in P. By symmetry, we may also assume elements c~2 and ~3. From Lemma 3 we obtain elements ~1,~2,~3~l ~ ~ and bl,b2,b3 . u~ ~ The bipartite order corresponding to these elements forms a copy of O~ in P.

3-INTERVAL IRREDUCIBLE PARTIALLY ORDERED SETS

115

Case 13. B(P) contains In. We also assume that B(P) does not contain a copy of Im when m < n. Choose an integer i with 2 ~ aj~ (aj2) and suppose that J2 5k Jl + 1. Assume, that ~: < d l and x < d2. It follows that bl, bn+3 E Inc(x) and B(P) contains a copy of Im for m < n. If x II d2 and Jz < n + 2, then

{aj~_,..., an+2} U {x, bjz+l,... , bn+3} U {c, d2} is a copy of Era for some m < n. We, therefore, assume that J2 "- n + l . I f x < dl, then {a~+2, b~+3, de, c, dl, x} generates a copy of D in B(P). Otherwise, if x II dl, then, by symmetry, we may also assume z > al. If x ~ bl, then {a,,+2, al, bl, c, dl, d2, x} generates a copy of FX2 in B(P). Again, by symmetry, we now assume x > b 1 and x > bn+3, but then {bl, dl, c, d2, bn+3, x} generates a crown A3 in B(P). Hence, we may assume elements by for 2 ~ a~ and bn+3 > a~, then {a~, b,~+3, d2, c, dl, bl) generates a copy of D in B(P). So we may assume, without loss of generality, that a~ II b +3. It follows easily, that B(P) contains Im where 0 ~ m < n, whenever there exists an integer j with bj > a~ and j ~ i, i + 1. From Lemma 3 we obtain elements b~, b,~+3, ~ e~ and bl,b,~+3, ~ u c",d~,d ~ in P. The bipartite order corresponding to these elements forms a copy of 77,~+1 in P.

Case 14. B(P) contains Gn. We also assume that B(P) does not contain a copy of Gin, Jm or I-Im when m < n. We first show that we may assume an element a~ when 2 ~ c and note that this implies x [I aj when i < j ~< n + 3 and x II bj when i - 1 ~< j < n + 3. Let i 7~ n + 2. If x < bn+3, then

{ai, a ~ + l , . . . , a~+3} U {bi, bi+l,..., bn+3} U {x} forms a copy of Gm for some m < n. Otherwise, if x ]l b,z+3, then the same set together with c generates Jm for some m < n. Now, let i = n + 2. If x < bn+3, then {bn+3, bn+2, bn+b x, a,~+2, a,~+3} forms a copy of D d. Otherwise, if z II bn+3, then the same set together with c generates CX d. Therefore, we may assume, that x II c and we have found an element ai i n P . We now show, that we may assume an element b~ when 2 ~ bi with ai, ai+l E Inc(x).

116

STEFAN FELSNER

Suppose, that z > c. If i > 2, then {al,...,ai}

U {bl,...,bi-l,X}

U {c}

forms a copy of Gm for s o m e m < n. Otherwise, if i = 2, then {al, a2, a3, bx, z, c} generates D. Therefore, x [] c and we have found an element b~ in P . We have s h o w n that we m a y assume elements a li and b~i for all 2 ~< i ~< n + 2. By duality, we m a y as well assume elements a i a n d b ~ ' i n P for a l l 2 ~ < i ~ < n + 2 . L ~ bn+3, ~ u Finally, f r o m L e m m a 3 we obtain elements an+3, bl, c~ and a~, an+3, b~, c u. The bipartite order corresponding to these elements forms a copy of Gn in P.

Case 15. B ( P ) contains J , . We also assume, that B ( P ) does not contain a copy of Gin, Jm or I-Ira w h e n m < n. In complete analogy with Case 14, we m a y assume elements a~L i n P w h e n 2 ~ <

i<~n+2. We n o w show, that we m a y assume an element b~ when 2 <~ i ~< n + 2. Choose a l o w - m a d e element x >/bl with at, ai+l E Inc(x). Suppose that z > c. If i > 2 and x > d, then

{al,...,ai}U

{bl,...,bi_l,X

)U {c}

forms a copy of Gm for s o m e m < n. If x 1[ d, then the same set together with d generates J m for s o m e rn < n. If i = 2 and z > d, then {al, a2, a3, bl, z, d} generate D. If z II d, then {al, a2, a3, bl, x, c, d) generates CX3. The contradiction shows that

]lc. We have shown that we m a y assume elements a lt a n d bi for all 2 ~< i ~< n + 2. By duality, we m a y as well assume elements a~' and b~ for all 2 <~ i ~< n + 2 in P . Finally, f r o m L e m m a 3 we obtain elements a~n+3, ~1,~~n+3,~l~-~ and a~, a~+3, b~, cu. The bipartite order corresponding to these elements forms a copy of ~,~ in P.

Case 16. B ( P ) contains Hn. We also assume that B ( P ) does not contain a copy of H,~ when m < n, nor G,~ or Jm when m ~< n. We first show that we m a y assume an element a~ when 1 ~ a~ with bt, bt+l E Inc(z). Assume that z > e. If i >/3, then {al,...,ai-l,x}

U { b l , . . . , b i ) U {c}

forms a copy of Gm for s o m e m < n. Otherwise, if i = 1, 2, then {bx, bz, b3, al, ~, c} forms a copy of D.

117

3-INTERVAL IRREDUCIBLE PARTIALLY ORDERED SETS

Assume that x > d. Let i # n. If z < bn+3, then

{ a i , . . . , a n + 2 } U {bi+l,...,bn+3} U {x} forms a copy of G,~ for some m < n. Otherwise, if z II bn+3, then the same set together with c generates J,~ for some m < n. If i = n + 1 and z < bn+3, then {bn+3, bn+2, bn+l, x, an+l, an+2} forms a copy of D d. Otherwise, if z 11 bn+3, then the same set together with d generates CX~. If i = n + 2, then {bn+l, bn+2, bn+3, d, x, an+2} forms a copy of D. Therefore, we may assume c, d E Inc(z) and have thus found an element a i. We now show that we may assume an element b~ when 2 ~i bi with ai-1, ai E Inc(z). Suppose that z > c and z > d, then {bl, a', b,~+3, d, z, e} forms a copy of D where a t is one of a i_ 1 or a{. Suppose x > c and x tl d; it follows that x I1 aj and z l[ bj when j > i. I f i < n + 2 then

( a i , . . . , an+2} U { h i , . . . , bn+3} [-.J{:g, d} generates Hm for some m < n. If i = n + 2, then {a,~+l, an+2, b,~+l, bn+2, bn+3, d, z ) generates C X d. Finally, let az > d and z

11e. If

i > 2, then

(al . . . . , a i - 1 ) U {bl, . . ., bi-1, x} U {c, d} generates tim for some m < n. If i = 2, then depending on z < bn+ 3 or z II bn+3, a copy of either CX1 or CX2 is formed by (al, an+2, bl, bn+3, e, d, x}. We, therefore, may assume c, d E Inc@) and have found elements b~ for 2 ~ bn+ 3 with an+2 [1 bn+ ' 3. If bn+ ' 3 > c, then {al, a,~+2, bl, bn+3, c, d, z} generate a copy of FX1. Therefore, we may assume an element bn+ 3 ill P. We have shown that we may assume elements a~ for 1 ~< / ~< n + 2 and be for 2 ~< i ~< n + 3. Dually, we may assume elements a~ for 1 ~< i ~< n + 2 and b~ in P for 1 ~< i ~< n + 2. Finally, from Lemma 3 we obtain elements c~, de and c ~', d u. The bipartite order corresponding to these elements forms a copy of 7-/,~ in P. 2.2. 34NTERVAL IRREDUCIBLE PARTIAL STACKS We begin this part with an analysis of the relation between the interval dimension of a bipartite order P and the interval dimension of partial stacks of P.

118

STEFAN FELSNER

LEMMA 5. Let P = (X, <) be a bipartiteposet and P ' = (X, <') be a partial stack of P. Then I d i m P I/> I d i m P . Proof Let I~,..., I~ be a interval-realizer of P'. Now tran_sfonn each of the interval orders I~ as follows. Extend the intervals of elements in Min(P) to the left to the leftmost endpoint of an interval in I~; symmetrically, extend the intervals of elements in Max(P) to the fight to the rightmost endpoint of an interval in I[. From this transformation we obtain a new family I 1 , . . . , I~ of interval orders. This family is an interval-realizer of P. Hence, Idim p / / > Idim P as claimed. [] As a consequence we can now sharpen the result of Theorem 4. THEOREM 7. If P = (X, < p ) is a 3-interval irreducible poset then P is a reduced

partial stack of some bipartite 3-interval irreducible poset. Proof From Theorem 4 we know that P contains a reduced partial stack of some bipartite 3-interval irreducible poset R = (Y, IdimR = 3. On the other hand, R* is a suborder of P, hence, 3 = I d i m P /> IdimR*. The irreducibility of P implies that X --" X 1 Y X 2 and, therefore, P =/~*. [] LEMMA 6. Let P = (X, <) be a bipartite order, then Idim P = Idim Stack(P). Proof From Lenuna 5 we obtain IdimStack(P) >t IdimP. As noted in the Introduction and proved in Theorems 1 and 2, Idim P = dim Stack(P). Together this gives IdimStack(P) >i dim Stack(P), the converse of this inequality is trivially valid for every order. [] Theorem 7 shows that a classification of 3-interval irreducible posets reduces to working with partial stacks of bipartite orders. We, therefore, require a suitable notation for these objects. REMARK. An intuitive approach to partial stacks of a (connected) bipartite poset P = (X, .U'(b) > L(b) for all b E B. The intervals (L'(z), U'(z)) then define an ordering P' = (X, <~,), such that, (A x B) n < p = (A x B) n
3-INTERVALIRREDUCIBLEPARTIALLYORDERED SETS

119

1 :'~ . . . . . . . . % I k ~ ::::::::':,'.'l . . . . :b~

bl :

iX

i

m

l

i

/i

/

!

c? t, L-.L....'e¢,. a~g.~...lo2 t

:

II

I

/ o

au

II

0

Fig. 3. A placementof the free-ends in C and the correspondingpartial stack of 0 2, i.e., a partial stack of P. For an example see Figure 3. Unfortunately the above construction will not lead to all partial stacks. As an example note that there are partial stacks of O2 with c~ > b~ but c~ 1t a~'. These partial stacks are not representable on B(O2). Therefore we require a more formal description of partial stacks. Let Succsp(x) (Predsp(z)) denote the successor sets (predecessor sets) of x in Stack(P). To describe a partial stack Q = (X,
Proof As I we take the interval order with 2n minimal elements {al~....,a2,~) and with 2n maximal elements { b l , . . . , bzn). The relations of I are: ai < bj exactly if i ~< j. Now fix a bipartite n-element poset R with miminal elements {zl . . . . . x~)

120

STEFANFELSNER

and maximal elements {Yl,..., Yn-k}. A partial stack IR containing/~ is given by: Pred(a~)=O

forl~
Pred(a0 = {al,...,ak) U{bj: xj <~rtYi}

for k < i <~ 2n,

Succ(bi)={bl:+l,...,b2n)U{ak+j: xi ~Ryj} Succ(b0 = O

forl~i~k,

fork
Note, that B(I) is a chain of length 2n + 2, while B(In) consists of a chain of length 2n + 3, where the element k + 1 has been substituted by a copy of B(R) without 0 and 1. [] As a consequence we obtain that the gap between the interval dimension of a bipartite poset P and the interval dimension of partial stacks of P can be arbitrarily high. We now turn to the partial stacks of 9m and 7-/m. There will be some indications, that the complete classification of 3-interval irreducible posers among the reduced partial stacks of these two orders might be intractable. THEOREM 8. Every bipartite poset Tt is a suborder of a partial stack QR of ~

(7~ra). Moreover, every bipartite 2-dimensional poset T~is a suborder of an 3-interval irreducible partial stack of ~ra (7"tin). Proof. We prove the theorem for partial stacks of 7/m. The idea behind the proof is the same as in the proof of Lemma 7. Let /~ be a bipartite n-clement poser with minimal elements { z l , . . . , z ~ ) and maximal elements {Yl,..., Yn-~). Also, let a copy of ~ n - 2 be given on the set {a~,..

.,

al

u

u

de)

U{a~, • . . , a~)U{ b u1 , " . , b ~ } U {

cu

,d~'}.

The relations of 7"/n-2 are: z ~ > yU exactly if x >/y in Hr~-2. A partial stack QR of 7-/,~_2 containing R is given by: Pred(a~)=O

forl<~i~
Pred(a~') = {a~: 1 ~<j ~< k) U {b~: 1 ~< j ~< k} U {a~.'~. xj <~R Yi} for k < i ~< n, Succ(a~) = { a~''3" k < j < n} U {b~: k < j < n + 1} U {a~: xi
fork
3-1NTERVALIRREDUCIBLE PARTIALLYORDERED SETS

121

All other dements z l have Succ(z *) = O and all other elements z" have Pred(z ~) = O. This gives a partial stack QR of 7-/m and the poset generated by the elements {af: 1 < i ~< k} O {a~: k < i ~< n} is isomorphic to R. + 2 be isomorphic to Hn-2 together with a new element e such that Let Hn_ Pred(e) = { a l , . . . , a~, b l , . . . , bk} and Succ(e) = {ak+l,... , an, b~+2, • •., bn+l}. The order B ( Q R ) is obtained by substituting e in H,~_ + 2 by a copy of B ( R ) without 0 and 1. If R is 2-dimensional, then we claim that QR is 3-interval irreducible. To verify this it suffices to consider the effect of point deletion in QR only on the essentially 3-dimensional part of B ( Q n ) , i.e., on H+_2 . [] REMARK. Let ttm = (X, <) and let the completion by cuts of tt,~ be denoted by L(It,~) = ( X U Y , <). A large class of 3-interval irreducible reduced partial stacks of 7-/m can be characterized by the following two properties: (1) B ( Q ) is an order isomorphic to L(lt,~) with elements of Y substituting by (possibly empty) 2-dimensional posets. (2) If x is l-labeled (u-labeled) in tim, then there is a unique element y E Q with L ( y ) = x ( U ( y ) = x).

Similar properties describe a large class of 3-interval irreducible reduced partial stacks of ~mHowever, there are more complex examples among the 3-irreducible partial stacks of 9m (7-/,0. Here is an example. EXAMPLE. Let C0 consist of the elements ~ a ~3' b~, bz, g b3, t c~} U { a lu, a 2u, a u3,b~, bu2, cU-t { a 2' J

and relation x l > yU exactly if x >~ y in Go. Let Q be the partial stack of C0 defined by: Succ(a

) = { aU 3,

b3}~

Succ(b~) = {a3, ~ b2, u b2, l b~3}, Pred(a~) = SaZ l 2, a ~ 2,a~,b~}, Pred(b~)

{a tL1, b~, b~).

122

STEFAN FELSNER

All other elements x l have Succ(x l) = O and all other elements x ~ have Pred(z u) = o . This gives a partial stack Q of ~0 which does not fall into the class of the previous remark. With these partial results we leave the classification of 3-interval irreducible reduced partial stacks of G,~ and 7-/m as an open problem. PROBLEM 1. Characterize the 3-interval irreducible reduced partial stacks of ~m and 7-Ira. We now turn to the partial stacks of the other bipartite 3-interval irreducible posets. With the next theorem we classify the 3-interval irreducible orders among them. THEOREM 9. Every partial stack of.An, O1, 02, 03, ~n, ~n, .~"0for every integer n >~ 0 and every partial stack of 3z~ (n > O) which has neither (an+ l 2 < bn+ L 2 and a~+2 II et) nor (b~ > a~ and b~ II is a 3-interval irreducible poset. Proof. The argument is again divided into a series of cases. As a criterion for the irreducibility of a candidate partial stack Q we use a technical lemma. L E M M A 8. Let P = (X, < p ) be a poset of interval dimension 3. Let Q = (Y,
Proof. We have to show that for every z E X the interval dimension of P~ is at most 2. To do this we exhibit a poset Q(x) of dimension 2 admitting an interval representation of P,:. Let x E X and let y~ be an element of Q such that x satisfies an essential label at y~. By duality we may suppose that x satisfies the label g at y~. We distinguish two cases.

Suppose, that y~ has two essential labels. Let R = (Z,
3-INTERVAL IRREDUCIBLE

PARTIALLY ORDERED

SETS

123

Z*(x') = U(y p~) if pl

: ¢t. Similarly, U*(x') : L(y~ ~) if Pl = ~ and U*(x') = U(y~ ~) if Pl = u. It is easy to verify that the mappings L*, U*: P~: ---+B(Ru~ ) indeed define an interval representation of P~. Next, suppose that there is no essential label at yr. Our assumptions imply that there is a unique element y~ covered by Yr. We claim that P~ has an interval representation on Qua. Since Q is 3-irrcducible we conclude that dim Qu. = 2 and, hence, that the interval dimension of P~ is 2. As mappings L*, U*: P:: -+ Qu~ choose the mappings induced by L, U: P --* ~), except for elements x t with U(x ~) = y~. For such an element let U*(x ~) = y~. Again, it is easy to verify that the mappings L*, U*: P~ --* Qu~ define an interval representation of P~. [] A

Case 1. P is a partial stack of .A~. Since Stack(.A, 0 = .An we obtain Q = .An and P is 3-interval irreducible.

Case 2. P is partial stack of 01. The partial stacks of O1 differ only in Succ(b~) for i = 1, 2, 3 which is either empty or {c~}. An interval representation on 1~ is obtained if we let U(b~) = ei when Succ(b~) = {e~) and else U(b~) = 1. These representations satisfy the conditions of Lemma 8 and, hence, P is 3-interval irreducible.

Case 3. P is a partial stack of 02, If Pred(e~) is one of^ {a~,b~} or {a u} or O and Pred(c~) is one of t~au, bu2} or {a ~ } or O, then B(P) = C. Moreover, the pair (P, C) satisfies the conditions of Lemma 8 and, therefore, P is 3-interval irreducible. If Pred(c~) is one of {a u, b~} or {a u } or O but Pred(c~) = {b~}, then B(P) = CX1d. Again, Lemma 8 yields the 3-interval irreducibility of P. By symmetry, we may now assume that Pred(e~) = {b~} and Pred(c~) = {b~}. Here, B(P) = CX d and again, P is 3-interval irreducible by Lemma 8.

Case 4. P is a partial stack of 03. All partial stacks of 03, together with interval representation on EX2 can be obtained by all possible choices of L(b~) E {al, 0}, L(b~) E {a2, 0}, U(b~) E {e, I) and U(a~) E {b2, 1). With Lemma 8 we then obtain the 3-interval irreducibility of P.

Case 5. P is a partial stack of g~. All partial stacks of £n, together with interval representations on E,~ can be obtained by all possible choice of L(b~) E {al, 0}, L(b,]+3 ) E {a,~+2,0} and for . . . , b,~+2, c ) either U(x) = d or U(x) = 1. These representations satisfy the conditions of Lemma 8 and, hence, P is 3-interval irreducible.

124

STEFAN FELSNER

Case 6. P is a partial stack of Zn. First, suppose that n = 0 and let D + be obtained from D by adding a new element d with d > b2 and d < ei, e2. We claim that every partial stack of 77o has an interval representation on D +. It should be clear that for i = 1, 3 we fred an appropriate point for U(b~) and L(b~) in D"~. It remains to consider U(b~). In Stack(770) the successor set of b~ is l*ela, ezl"2sand, hence, Succp(b~) C {c~,c~). If Succp(b~) -- {e~,e~}, then let U(b~) = d. If Succp(b~) = ( ~ } with i = 1 or i = 2, then let U(b~) = ei. Finally, if Succp(b~) = ~, then let U(b~) = 1. With a slight generalization of Lemma 8 we obtain the 3-interval irreducibility of P. Now, let n > 0 and let I + be obtained from I,~ by adding a new element e with e < d l , e < d2, e > e and e > bi for i = 2 , . . . , n + 2. An analysis as in the previous case shows~.,that every partial stack of Z,~ has an interval representation on I +. (Note that I + = L(I~).) Again, the 3-interval irreducibility of P follows from the generalization of Lemma 8.

Case 7. P is a partial stack of Yo. If Pred(b~) is one of {a~, c~'} or {d'} or O and Succ(a~) is one of :b 2, e el lj o r or ~, then B(P) = F0. Moreover, the pair (P, F0) satisfies the conditions of Lemma 8 and, therefore, P is 3-interval irreducible. IfPred(b~) is one of {a~,e ~ } or {c~ } or O but Succ(a~) = { b2}, e then B(P) = FX~. Again, Lemma 8 yields the 3-interval irreducibility of P. By symmetry we may now assume that Pred(b~) = {a~} and Succ(a~) = {b~}. A

Here, B(P) = FXza and P is 3-imerval irreducible by Lemma 8.

Case 8. P is a partial stack o f Sn with n > O. Suppose that Succp(a~+z) = {b,~+2 l }. The bipartite subposet of P with milfimal elements { a ~ , . . . , a~+2, by, d ~) and {b~, • • -, ben+2,d~, el) as maximal elements forms a copy of Sn-1. If we remove c~' and an+ ~ 2 from P to obtain P - , then P - is a partial stack of Cn-1. Therefore, P is not irreducible. We may now assume that Succp(a~+2) is either {b,~+2,lel} or {e t} or 0. Dually, we may assume that Predp(b~) is {a~, c~) or {c ~) or o . It follows that B(P) = Fn and with Lemma 8 that P is 3-interval irreducible.

References 1. Dushnik, B. and Miller, E. (1941) Partially ordered sets, Amer J. Math. 63, 600--610. 2. Felsner, S., Habib, M. and Mthring, R. H. (1991) On the interplay of interval dimension and dimension, Preprint 285, TU-Berlin. 3. Fishburn, P. C. (1985) Interval Orders and lnterval Graphs, Wiley, New York. 4. Kelly, D. (1977) The 3-irreducible partially ordered sets, Can. J. Math. 29, 367-383. 5. Kelly, D. and Rival, I. (1975) Planar lattices, Can. J. Math. 27, 636--665. 6. Kelly, D. and Trotter, W. T. (1982) Dimension theory for ordered sets, in Ordered Sets, I. Rival (ed.), D. Reidel Publishing Comp., Dordreeht, pp. 171-212. 7. Mitas, J. (1992) Interval representations on arbitrary ordered sets, Preprint, Darmstadt.

3-INTERVAL IRREDUCIBLE PARTIALLY ORDERED SETS

125

8. Trotter, W. T. and Moore, J. I. (1976) Characterization problems for graphs, partially ordered sets, lattices and families of sets, Discrete Math. 16, 361-381. 9. Trotter, W. T. (1981) Stacks and splits of partially ordered sets, Discrete Math. 35, 229-256. 10. Trotter, W. T. (1991) Combinatoricsand Partially Ordered Sets: Dimension Theory, Johns Hopkins Press.