Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 741.06001
Autor: Erdös, Paul; Kierstead, H.A.; Trotter, W.T.
Title: The dimension of random ordered sets. (In English)
Source: Random Struct. Algorithms 2, No.3, 253-275 (1991).
Review: In this important paper the authors introduce and study in some detail the space of random bipartite posets \Omega = \Omega(n,p) with typical elements P = (A\cup A', <), A = {a1,...,an}, A' = {a1',...,an'} and if P has q relations ai < aj', Pr(P) = pq(1-p)n2-q, with 0 \leq p \leq 1. The object of the study undertaken here is to facilitate construction of posets with small maximum degree and cardinality but with large dimension, other than the standard example sn consisting of the 1-subsets as well as the (n- 1)-subsets of an n-set ordered by set inclusion. After developing a quantity of basic general theory on \Omega(n,p) and a great deal of further very delicate work, the authors establish the following key result:
(T.3.1): Let t = t(n) be a non-negative function of n, let p = p(n) be a function of n with 0 \leq p \leq 1. Suppose that: (1) limn ––> oonp = oo; (2) limn ––> oot/p(n-t) = oo; (3) limn ––> oo\exp[\alpha][1-(1-p)\exp[\beta]]\gamma = 0, with \alpha = 4t log n log np/p, \beta = -24t/p(n-t), \gamma = p2(n-t)3/512 log2np. Then dim P > t for almost all P in \Omega(n,p).
Using this theorem, then, given \epsilon > 0 and t = \delta np log np/(1+\delta p log np), a careful computation/estimate yields the authors' (T.1.5): For every \epsilon > 0, there exists a \delta > 0 so that if (log1+\epsilonn)/n < p, 1-n-1+\epsilon, then dim P > t for almost all P in \Omega(n,p). Using (T.1.5) other inequalities are obtained which are useful in dimension estimates. The results reported here are compared to other obtained by Füredi and Kahn using probabilistic techniques. Furthermore, the authors use methods of Kleitman and Rothschild and some related to those developed by themselves to obtain inequalities for the space of labelled posets on n points uniformly distributed as in (T.1.7): There exist absolute constants c1,c2 > 0 so that: n/4(1-c1/ log n) < dim P < n/4(1-c2/ log n), for almost all labeled posets on n points. They close the paper with a collection of remarks and questions which will be points of departure for further developments in dimension theory for random posets of different types.
Reviewer: J.Neggers (Alabama)
Classif.: * 06A06 Partial order
05C80 Random graphs
68R99 Discrete mathematics in relation to computer science
Keywords: random bipartite posets; large dimension; random posets
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag