Spherical containment and the Minkowski dimension of partial orders

The recent work on circle orders generalizes to higher dimensional spheres. As spherical containment is equivalent to causal precedence in Minkowski space, we define the Minkowski dimension of a poset to be the dimension of the minimal Minkowski space into which the poset can be embedded; this isd if the poset can be represented by containment with spheresS ^d–2 and of no lower dimension. Comparing this dimension with the standard dimension of partial orders we prove that they are identical in dimension two but not in higher dimensions, while their irreducible configurations are the same in dimensions two and three. Moreover, we show that there are irreducible configurations for arbitrarily large Minkowski dimension, thus providing a lower bound for the Minkowski dimension of partial orders.     

Decomposition of partial orders

A decomposition theory for partial orders which arises from the split decomposition of submodular functions is introduced. As a consequence of this theory, any partial order has a unique decomposition consisting of indecomposable partial orders and certain highly decomposable partial orders. The highly decomposable partial orders are completely characterized. As a special case of partial orders, we consider lattices and distributive lattices. It occurs, that the highly decomposable distributive lattices are precisely the Boolean lattices.     

Some inequalities for partial orders

We establish some inequalities connecting natural parameters of a partial order P. For example, if every interval [a,b] contains at most maximal chains, if some antichain has cardinality v, and if there are ₁ chains whose union is cofinal and coinitial in P, then the chain decomposition number for P is ₁v (Theorem 2.2), and the inequality is sharp in a certain sense (Section 3).This paper was written while the authors were visitors at the Laboratoire d'algèbre ordinale, Département de Mathématiques, Université Claude Bernard, Lyon 1, France.Research supported by NSERC grant # A5198.     

Random orders of dimension 2

A relationship is established between (partially) ordered sets of dimension 2 chosen randomly on a labelled set, chosen randomly by isomorphism type, or generated by pairs of random linear orderings. As a consequence we are able to determine the limiting probability (in each of the above sample spaces) that a two-dimensional order is rigid, is uniquely realizable, or has uniquely orientable comparability graph; all these probabilities lie strictly between 0 and 1. Finally, we show that the number of 2-dimensional (partial) orderings of a labelled n-element set is .On leave from Emory University, Atlanta, GA. Research at Emory supported by ONR grant N00014 85-K-0769.     

Linear extensions of partial orders preserving monotonicity

Given a poset (A, r) and an acyclic r-monotone function f: AA, we prove that r can be extended to a linear order R with xRyf(x)Rf(y) for all x, yA.     

Asymptotic enumeration ofN-free partial orders

LetN(n) andN ^* (n) denote, respectively, the number of unlabeled and labeledN-free posets withn elements. It is proved thatN(n)=2 ^{n logn+o(n logn)} andN ^*(n)=2^{2n logn+o(n logn)}. This is obtained by considering the class ofN-free interval posets which can be easily counted.     

On the Boolean dimension of spherical orders

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.Part of this work was carried out while both authors were visiting the Department of Applied Mathematics (KAM) of Charles University, Prague. The authors acknowledge support from the EU HCM project DONET.     

On the dimension of the cartesian product of relations and orders

It is known that for incidence structures and , max , wheref dim stands for Ferrers relation. We shall show that under additional assumptions on and , both bounds can be improved. Especially it will be shown that the square of a three-dimensional ordered set is at least four-dimensional.     

On the greedy dimension of a partial order

This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poset has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poset and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices.     

Transitive closure for restricted classes of partial orders

Most papers dealing with partial orders assume that the input is given either in transitively closed or transitively reduced form. In this paper, we show that it is possible to solve some problems on partial orders in less time than it takes to perform transitive closure or reduction for general graphs. In particular, we present efficient algorithms for recognizing two dimensional partial orders and N-free partial orders when no assumptions are made about the form of the input.This work was supported by National Science Foundation Grant DCR-8604577 and the Vanderbilt University Research Council.     

The dimension of cycle-free orders

The existence of a four-dimensional cycle-free order is proved. This answers a question of Ma and Spinrad. Two similar problems are also discussed.Research partially supported by Office of Naval Research grant N00014-90-J-1206Research partially supported by the National Science Foundation under grant DMS     

Connectedness and diameter for random orders of fixed dimension

Let P _k (n) be the (partial) order determined by intersecting k random linear orderings of a set of size n; equivalently, let P _k (n) consist of n points chosen randomly and independently from the unit cube in ^k , with the induced product order. We show for each fixed k>1, that with probability approaching 1 as n, the comparability graph of P _k (n) is connected and has diameter 3.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

Interval orders and circle orders

A finite poset is an interval order if its point can be mapped into real intervals so that x in the poset precisely when x's interval lies wholly to the left of y's; the poset is a circle order if its points can be mapped into circular disks in the plane so that x precisely when x's circular disk is properly included in y's. This note proves that every finite interval order is a circle order.     

Degrees of freedom versus dimension for containment orders

Given a family of sets L, where the sets in L admit k degrees of freedom, we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)nk log n where k is fixed and n is large.Research supported in part by Allon Fellowship and by a grant from Bat Sheva de Rothschild Foundation.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.     

Circle orders and angle orders

A poset is a circle order if its points can be mapped into circular disks in the plane so that x in the poset precisely when x's circular disk is properly included in y's; the poset is an angle order if its points can be mapped into unbounded angular regions that preserve < by proper inclusion. It is well known that many finite angle orders are not circle orders, but has been open as to whether every finite circle order is an angle order. This paper proves that there are finite circle orders that are not angle orders.     

The number of partial orders of fixed width

We investigate the approximate number of n-element partial orders of width k, for each fixed k. We show that the number of width 2 partial orders with vertex set {1, 2, ..., n} is

Two properties of projective orders

We prove a closure property of the class of projective orders without infinite chains, and strengthen Larose's theorem on the equivalence between projectivity and quasiprojectivity for finite orders.     

Line directionality of orders

Some orders can be represented by translating convex figures in the plane. It is proved thatN-free and interval orders admit such representations with an unbounded number of directions. Weak orders, tree-like orders and two-dimensional orders of height one are shown to be two- directional. In all cases line segments can be used as convex sets.     

Weak orders admitting a perpendicular linear order

Two orders on the same set are perpendicular if the constant maps and the identity map are the only maps preserving both orders. We characterize the finite weak orders admitting a perpendicular linear order.