The dimension of random ordered sets

P. Erdos, Henry Kierstead, W. T. Trotter

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


Let P = (X, <) be a finite ordered set and let |P| denote the cardinality of the universe X. Also let Δ(P) denote the maximum degree of P, i.e., the maximum number of points comparable to any one point of P. Füredi and Kahn used probabilistic methods to show that the dimension of P satisfies dim(P)≦ c1 Δ(P)log|P| and dim(P) ≦ c2ΔP log2Δ(P) where c, and c2 are positive absolute constants. In this article, we consider the probability space Ω(n, p) of bipartite ordered sets having n minimal elements and n maximal elements, where the events that any minimal element is less than any maximal element are independently distributed and each has probabilityp =p(n). We show that for every ϵ >0, there exist δ, c > 0 so that: (1) if (log1+ϵn)/n<p < 1/log n, then dim(P)∈ Ωpn log pn for almost all P∈ Δ(n, p); and (2) if 1/log n ≦ < 1 − n−1+ϵ, then dim(P) >n‐ cnlp log n for almost all P ∈Ω(n, p). The first inequality is best possible up to the value of the constant δ when p > (log2+en)/n. As to the accuracy of the second inequality, we have the trivial upper bound dim(P)≦n for all P∈Ω(n, p). We then develop a nontrivial upper bound which holds for almost all P ∈Ω(n, p), when p ≧ 1 /log n. This upper bound has the same form as the lower bound when p is constant. We also study the space ℒ(n) of all labelled ordered sets on n points and show that there exist positive constants c1, c2 so that n/4 ‐ c1n/log n < dim(P) <c2 n/4 ‐ c2n/log n for almost all P ∈ ℒ(n).

Original languageEnglish (US)
Pages (from-to)253-275
Number of pages23
JournalRandom Structures & Algorithms
Issue number3
StatePublished - 1991

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'The dimension of random ordered sets'. Together they form a unique fingerprint.

Cite this