ISSN:
1572-9273
Keywords:
06A10
;
Partially ordered set
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Let P be a partially ordered set. Define k = k (P) = max p∈ |{x ∈ P : p 〈 x or p = x}|, i.e., every element is comparable with at most k others. Here it is proven that there exists a constant c (c 〈 50) such that dim P 〈 ck(log k)2. This improves an earlier result of Rödl and Trotter (dim P ≤2 k 2+2). Our proof is nonconstructive, depending in part on Lovász' local lemma.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00403406
Permalink