Box-spaces and random partial orders
HTML articles powered by AMS MathViewer
- by Béla Bollobás and Graham Brightwell PDF
- Trans. Amer. Math. Soc. 324 (1991), 59-72 Request permission
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
- Béla Bollobás and Peter Winkler, The longest chain among random points in Euclidean space, Proc. Amer. Math. Soc. 103 (1988), no. 2, 347–353. MR 943043, DOI 10.1090/S0002-9939-1988-0943043-6
- Peter Winkler, Random orders, Order 1 (1985), no. 4, 317–331. MR 787544, DOI 10.1007/BF00582738
- Peter Winkler, Connectedness and diameter for random orders of fixed dimension, Order 2 (1985), no. 2, 165–171. MR 815862, DOI 10.1007/BF00334854
- Joyce Justicz, Edward R. Scheinerman, and Peter M. Winkler, Random intervals, Amer. Math. Monthly 97 (1990), no. 10, 881–889. MR 1079974, DOI 10.2307/2324324
Additional Information
- © Copyright 1991 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 324 (1991), 59-72
- MSC: Primary 60D05; Secondary 06A07
- DOI: https://doi.org/10.1090/S0002-9947-1991-0986685-9
- MathSciNet review: 986685