ISSN:
1572-9273
Keywords:
06A07
;
68P20
;
Boolean dimension
;
planar poset
;
spherical poset
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract It is well known that if a planar order P is bounded, i.e. has only one minimum and one maximum, then the dimension of P (LD(P)) is at most 2, and if we remove the restriction that P has only one maximum then LD(P)≤3. However, the dimension of a bounded order drawn on the sphere can be arbitrarily large. The Boolean dimension BD(P) of a poset P is the minimum number of linear orders such that the order relation of P can be written as some Boolean combination of the linear orders. We show that the Boolean dimension of bounded spherical orders is never greater than 4, and is not greater than 5 in the case the poset has more than one maximal element, but only one minimum. These results are obtained by a characterization of spherical orders in terms of containment between circular arcs.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00338743
Permalink
