[2] x [3] x N is not a circle order

Order 8: 243-246, 1991. 0 1991 Kluwer Academic

243 Publishers.

Printed

in the Netherlank

[2] x [ 31 x N is not a Circle Order CHIANG

LIN

Department

of Mathematics,

Communicated

National

Central

University,

Chung-Li,

Taiwan,

R.O.C.

by I. Rival

(Received: 30 October 1989; accepted: 30 May 1991) The result stated in the title is proved in this note. Actually we show that S x N is not a circle order, where S = {( 1, I), (1,2), (1,3), (2, I), (2, 3)}. Furthermore this non-circle order is critical in the sense that (S - {x}) x N is a circle order for any x in S. Abstract.

AMS Key

subject words.

classification

(1991).

06A06.

Poset, circle order, dimension.

1. Introduction A poset P is called a circle order if one can assign to each x E P a circular disc C, such that x < y in P -S C, c C,,. It is asked [3] whether every three-dimensional poset is a circle order. For finite posets this problem is still open. As for infinite posets this is much simpler. Scheinerman and Wierman [2] proved that [n] x [n] x N is not a circle order for some large n, where [n] is the poset { 1 < 2 < 3 < * * * < rz} andNistheposet(1<2<3<-. a}. And then Hurlbert [l] gave a short proof that N x N x N is not a circle order. In this note we will show that [2] x [3] x N is not a circle order. Actually we prove that {( 1, l), ( 1,2), ( 1,3), (2, l), (2,3)} x N is not a circle order. First we introduce a notation. If P = (X, <) is a poset then let P^ denote the poset with X as underlying set such that x < y in p o y < x in P. Let us begin with a lemma. LEMMA

1. Suppose P is a circle order. Then p is a circle order if one of the following conditions ho&. (1) P is Jinite. (2) For any x, y E P, there exists z E P such that z < x and z < y. Proof. For a point Q in the plane E* and a positive number r, we let C(Q; r) denote the circular disk with center Q and radius r. Let (C(QX; rX) 1x E P} be a circular disk representation of P such that C(Q, ; r,) is the circular disk corresponding to x. If d > 0, it is easy to see that {C(Q x ; r, + d) 1x E P} is still a circular disk representation of P. We may assume that P has a circular disk representation such that the intersection below.

of the interiors of all disks is nonempty.

This is explained

244

CHIANG

LIN

(1) If P is finite, then it is easy to see that there exists d > 0 such that 0, E p interior of C(QX ; r, + d) # 0. (2) If for any X, y E P, there exists z E P such that z < x and z < y, then for any x1,x2, * * * 3 x,~P,thereexistsz~Psuchthatz~x,,z~x~,...andzdx,,and hence ni = ,,2,..,,nC(Q,; r,,) # 0. Since each disk is a compact subset of E*, we have interior of C(QX ; r, + d) # 0 for any d > 0. If C is a circular disk in the plane E* and the boundary of C does not contain the origin of E*, we denote by C the circular disk whose boundary equals (x/]\x~/* 1x E boundary of C>. Let {CX I x E P> be a circular disk representation of P such that nxeP interior of C, # 0. We may assume that the origin of the plane is in the interior of each C,. Then it is easy to see that {c I x E P} is a disk representation of P. 0

nx.PC Z0.Hence fLp

In fact we will use Lemma 1 only for Condition question. QUESTION.

(2). Here we have a subsidiary

Suppose P is a circle order. Does this imply that P is a circle order?

2. Main Results THEOREM 2. {( 1, 1), ( 1,2), (1, 3), (2, 1), (2,3)) x N is not a circle order. Proof. Let P = {( 1, 1), (1,2), ( 1,3), (2, l), (2, 3)) x N. Since P contains a least element, it follows from Lemma l(2) that we only need to show that P is not a circle order. We can see that P is isomorphic to Q, where Q = ((1, 11, (1,3), (2, 11, (2,2), (293)) x -N. We will show that Q is not a circle order. Suppose, on the contrary, that Q is a circle order. Let C(i, j, -k) be a circular disk for each (i, j, -k) E Q such that C(i, j, -k) c C(i’, j’, -k’)o (i, j, -k) < (i’, j’, -k’). Define C(i,j) = hEN C(i, j, -k). For circular disks C, and C, we say that C, is internally tangent to C, if C, is properly contained in C,, and C, is tangent to C,. As the arguments in [2] we have ( 1) each C(i, j) is a circular disk (furthermore we may assume each C(i, j) is a nondegenerate disk, since we can add a positive constant to the radius of each C(i, j, -k)) and (2) C(i, j) is either equal or internally tangent to C(i’, j’) if (i, j) < (i’, j’). Hence C( 1, 1) is either equal or internally tangent to C(2,3). Then either C(2, 1) = C( 1,3) or C(2, 1) is tangent to C( 1, 3), since C(1, 1) c C(1, 3) E C(2, 3) and C(1, 1) E C(2, 1) E C(2, 3). CLAIM. (1) C(2, 1) = C(1, 3); (2) each C(2, 1, -n) is tangent to C(2, 1). We check the claim as follows. (1) Suppose, on the contrary, that C(2, 1) # C( 1, 3). Assume, without loss of generality, that C(2, 1) is internally tangent to C( 1, 3), say at a point z. Then, C( 1, 3, -n) is tangent to C( 1, 3) at z for all n in N, otherwise C(2, 1, -Z) c C( 1, 3, -m) for some l, m in N, which is impossible. On the other hand C( 1, 1) is internally tangent to C( 1, 3) at z. This follows from the facts that C( 1, 1) E C(2, 1) and C(2, 1) is internally tangent to C( 1,3) at z

[2] x [3] x N IS NOT A CIRCLE ORDER

245

and C( 1, 1) is either equal or internally tangent to C( 1,3). Therefore C( 1, 1, -n) is either equal or tangent to C( 1, 3) at z for all n, since C( 1, 1) c C( 1, 1, -n) c C(173, -n). Hence, for any m, n in N, either C(l, 1, -n) c C(l, 3, -m) or C(L 3, -m) G C( 1, 1, -n), which is impossible if n < m. This contradiction confirms Claim (1). (2) Suppose C(2, 1, -n) is not tangent to C(2, 1) for some n. Then C( 2, 1, -n) 3 C( 1, 3, -m) for some m, which is impossible. This contradiction confirms Claim (2). Similarly, we also have C( 2,2) = C( 1, 3) and each C(2,2, -n) is tangent to C(2,2). Let C = C(2,2) = C( 1, 3) = C( 2, 1). Suppose each C( 2, 1, -n) is tangent to C at a point x and each C(2,2, -n) is tangent to C at a point y. We consider two cases. Case 1. x = y. Then for all m, n in N, either C(2, 1, -n) c C( 2,2, -m) or C(2,2, -m) E C(2, 1, -n), which is impossible when n < m. Case 2. x # y. Then C(2, 1, -n) and C(2,2, -n) are not contained in each other, which is impossible. This completes the proof of the theorem. 0 The non-circle order in Theorem 2 is critical in the following sense. Let S be the poset {(l,l), (1,2), (1,3), (2, l), (2,3)}. Then (S - {x}) x N is a circle order for any x E S. This is explained as follows. If x = (1, 3) or (1,2), then (S - {x}) x N is isomorphic to [2] x [2] x N, which is a circle order because of Theorem 3. Otherwise (S - (xl) x N is either a product of two nontrivial chains or one of the two posets in Theorem 4(3), and these posets are circle orders because of Theorem 4. THEOREM 3. [2] x [ 21 x N is a circle order. Proof. It suffices to show that [2] x [2] x -N is a circle order because of Lemma l(2). In the following we will assign a circular disk C(i,j, -n) in the plane E2 for each (i,j, -n) E [2] x [2] x -N so that (i,j, -n) < (i’,j’, -n’) o C(i,j, -n) c C(i’,j’, -n’). Let C(2,2, - 1) be the disk with ( -2,O), (2,O) E E2 as the end points of its diameter, and C(2, 1, - 1) the disk with ( - 2,0), ( 1,0) E E2 as end points of its diameter, and C( 1,2, - 1) the disk with ( - LO), (2,O) E E2 as the end points of its diameter. Define C( 1, 1, -n), C(2,2, --n - l), C(1,2, --n - l), C(2, 1, --n - 1) from C( 1,2, -n), C( 2, 1, -n) recursively as follows. Let C( 1, 1, -n) be the disk lying below X-axis with its boundary passing through (0, - l), and internally tangent to C(l, 2, -n) and C(2, 1, -n). Let (0, t) E E2 be the center of C(l, 1, -n). Let C(2, 1, -n - 1) be the disk internally tangent to C(2, 1, - 1) at (1,0) and tangent to the line y = ( - 1 + t)/2. Let C( 1,2, --n - 1) be the disk internally tangent to C( 1,2, - 1) at ( - 1,0) and tangent to the line y = ( - 1 + r)/2. And lastly C(2,2, --n - 1) is the disk with its center at (0,O) and its boundary passing through (0, t). We can see that C( 2, 1, -n - 1) and C( 1,2, -n - 1) are internally tangent to C(2,2,-n-l).Itisnothardtocheckthat{C(i,j,-n)(l~i~2,1~j~2,n~N} is a disk representation for [2] x [2] x -N, and this completes the proof. q

246

CHIANG

LIN

THEOREM

4. (1) Every two-dimensional countable poset is a circle order. (2) The product of two nontrivial chains is a two-dimensional poset.

(3) The posets ((1, 11, (1,2), (1,3), (2, I>} XN and {tL2),

tL3),

(2,3), (2, 1))

x N are both two-dimensional. Proof. (1) Let P be a 2-dimensional countable poset. Suppose rr, , z2 are two linear extensions realizing P, i.e., q, rr2 are functions with n, : P + R + and n2: P + R+ such that x < y in P o n,(x) < q(y) for i = 1,2. Now for each x E P let C, be the circular disk in the plane E* with (-A,(X), 0), (n,(x), 0) l E* as the end points of its diameter. It is each to see that {CX 1x E P> is a disk representation for P.

(2) is trivial. (3) Let ~5, L2 be linear extensions of the L,={(1,1,1)~(1,2,1)c(1,3,1)~(1,1,2)~(1,2,2)~(1,3,2)~~~~~(1,1,n) <(1,2,n)<(l,3,n)<...<(2,1,1)<(2,1,2)<.,.<(2,1,n)<...)

first

poset

such

that

and L,=

*.*<(1,2,n) <*a .<(1,3,1)<(1,3,2)<*..<(1,3,n)<***}. It is easy to see that L, and L, realize the first poset. Hence the first poset which is not a chain is two-dimensional. The proof for the second poset is similar. cl Acknowledgment The author would like to thank one of the referees for his helpful suggestions which improved the readability of this paper. References 1. G. H. Hurlbert (1988) A short proof that N3 is not a circle order, Order 5, 235-237. 2. E. R. Scheinerman and J. C. Wierman (1988) On circle containment orders, Order 4, 315-318. 3. W. T. Trotter (1986) Problems and conjectures in combinatorial theory for ordered sets, preprint.