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) less than or equal to 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.
On the Boolean dimension of spherical orders / G. R., Brightwell; Franciosa, Paolo Giulio. - In: ORDER. - ISSN 0167-8094. - STAMPA. - 13:3(1996), pp. 233-243.
On the Boolean dimension of spherical orders
FRANCIOSA, Paolo Giulio
1996
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) less than or equal to 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
