Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Box-spaces and random partial orders

Authors: Béla Bollobás and Graham Brightwell
Journal: Trans. Amer. Math. Soc. 324 (1991), 59-72
MSC: Primary 60D05; Secondary 06A07
MathSciNet review: 986685
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 60D05, 06A07

Retrieve articles in all journals with MSC: 60D05, 06A07

Additional Information

Article copyright: © Copyright 1991 American Mathematical Society