Finite three dimensional partial orders which are not sphere orders
28 April 1999
Given a partially ordered set P = (X,P), a function F which assigns to each x is an element of X a set F(x) so that x less than or equal to y in P if and only if F(x) subset of or equal to 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 is an element of 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 intervals from R consists of those posets which have dimension at most two. But when d greater than or equal to 2, some posets of arbitrarily large dimension have inclusion representations using spheres in R-d. However, using a theorem of Alon 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 has 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. (C) 1999 AT&T Information Services. Published by Elsevier Science B.V. All rights reserved.