Box-spaces and random partial orders

Abstract:

Winkler [2] studied random partially ordered sets, defined by taking $n$ points at random in ${[0,1]^d}$, with the order on these points given by the restriction of the order on ${[0,1]^d}$. Bollobás and Winkler [1] gave several results on the height of such a random partial order. In this paper, we extend these results to a more general setting. We define a box-space to be, roughly speaking, a partially ordered measure space such that every two intervals of nonzero measure are isomorphic up to a scale factor. We give some examples of box-spaces, including (i) ${[0,1]^d}$ with the usual measure and order, and (ii) Lorentzian space-time with the order given by causality. We show that, for every box-space, there is a constant $d$ which behaves like the dimension of the space. In the second half of the paper, we study random partial orders defined by taking a Poisson distribution on a box-space. (This is of course essentially the same as taking $n$ random points in a box-space.) We extend the results of Bollobás and Winkler to these random posets. In particular we show that, for a box-space $X$ of dimension $d$, there is a constant ${m_X}$ such that the length of a longest chain tends to ${m_X}{n^{1/d}}$ in probability.