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 **R**^{d}, *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 **R**^{d}. However, using
a theorem of Alan and Scheinerman, we know that not all posets of
dimension *d* +2 have inclusion representations using spheres in
**R**^{d}. In 1984, Fishburn and Trotter asked whether
every finite 3-dimensional poset had an inclusion representation using
spheres (circles) in **R**^{2}. 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