# Three Dimensional Partial Orders which are not Sphere Orders

### Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: felsner@inf.fu-berlin.de Peter C. Fishburn AT & T Labs Research C227, 180 Park Avenue Florham Park, NJ 07932, U.S.A. email: fish@research.att.com William T. Trotter Department of Mathematics Arizona State University Tempe, AZ 85287, U.S.A. email: trotter@ASU.edu Report B 97-11 November 1997

Given a partially ordered set P = (X,P), a function F which assigns to each $x \in X$ a set F (x) so that $x \leq y$ in P if and only if $F (x) \subseteq F (y)$ is called an inclusion representation. Every poset has such a representation, so it is natural to consider restrictions on the nature of the images of the function F. In this paper, we consider inclusion representations assigning to each $x \in X$ a sphere in Rd, d-dimensional Euclidean space. Posets which have such representations are called sphere orders. When d =1, a sphere is just an interval from R, and the class of finite posets which have an inclusion representation using using intervals from R consists of those posets which have dimension at most two. But when d >=2, some posets of arbitrarily large dimensions have inclusion representations using spheres in Rd. However, using a theorem of Alan and Scheinerman, we know that not all posets of dimension d +2 have inclusion representations using spheres in Rd. In 1984, Fishburn and Trotter asked whether every finite 3-dimensional poset had an inclusion representation using spheres (circles) in R2. In 1989, Brightwell and Winkler asked whether every finite poset is a sphere order and suggested that the answer was negative. In this paper, we settle both questions by showing that there exists a finite 3-dimensional poset which is not a sphere order. The argument requires a new generalization of the Product Ramsey Theorem which we hope will be of independent interest.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-97-11.ps.gz