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