New results from an algorithm for counting posets

In this paper we report on the success of a new technique for computing the number of unlabeled partial orders on n elements based on the partial order of partial orders ordered by containment. In addition to the number of partial orders, we obtain complete enumerations of the number of partial orders on n elements with r relations for n<-11, where r takes on all possible values. We point out some interesting sequences that arise in these tables.Supported by Natural Sciences and Engineering Research Council Grant No. OGP8053.     

Simplicial elimination schemes,extremal lattices and maximal antichain lattices

Fix a partial order P=(X, <). We first show that bipartite orders are sufficient to study structural properties of the lattice of maximal antichains. We show that all orders having the same lattice of maximal antichains can be reduced to one representative order (called the poset of irreducibles by Markowsky [14]). We then define the strong simplicial elimination scheme to characterize orders which have distributive lattice of maximal antichains. The notion of simplicial elimination corresponds to the decomposition process described in [14] for extremal lattices. This notion leads to simple greedy algorithms for distributivity checking, lattice recognition and jump number computation. In the last section, we give several algorithms for lattices and orders.     

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.     

Treewidth of cocomparability graphs and a new order-theoretic parameter

We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively.This work was done while the second author stayed at the LIRMM within the PROCOPE program of the DAAD. Both authors acknowledge the support by the PROCOPE program. The second author also acknowledges partial support by the Deutsche Forschungsgemeinschaft under Grant No Mo446/3-1.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.     

Linear Orders on General Algebras

We answer the question, when a partial order in a partially ordered algebraic structure has a compatible linear extension. The finite extension property enables us to show, that if there is no such extension, then it is caused by a certain finite subset in the direct square of the base set. As a consequence, we prove that a partial order can be linearly extended if and only if it can be linearly extended on every finitely generated subalgebra. Using a special equivalence relation on the above direct square, we obtain a further property of linearly extendible partial orders. Imposing conditions on the lattice of compatible quasi orders, the number of linear orders can be determined. Our general approach yields new results even in the case of semi-groups and groups.     

A counterexample in the theory of random orders

We show that the 0–1 law fails in random orders of fixed dimension k, k3. In particular, we give an example of a first-order sentence , in the language of partial orders, which cannot have limiting probability 0 or 1 among random orders of dimension 3.Research supported by ONR grant N00014-85-K-0769     

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.     

Angle orders and zeros

An angle order is a partially ordered set whose points can be mapped into unbounded angular regions in the plane such that x is less than y in the partial order if and only if x's angular region is properly included in y's. The zero augmentation of a partially ordered set adds one point to the set that is less than all original points. We prove that there are finite angle orders whose augmentations are not angle orders. The proof makes extensive use of Ramsey theory.     

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.     

Fixed points of posets and clique graphs

The fixed point property for partial orders has been the object of much attention in the past twenty years. Recently, M. Roddy ([7]) proved this famous conjecture of Rival (see [6]): the class of finite orders with the fixed point property is closed under finite products.In this article, we prove that a finite order has the fixed point property if the sequence of iterated clique graphs of its comparability graph tends to the trivial graph.     

A 3/2-approximation algorithm for the jump number of interval orders

The jump number of a partial order P is the minimum number of incomparable adjacent pairs in some linear extension of P. The jump number problem is known to be NP-hard in general. However some particular classes of posets admit easy calculation of the jump number.The complexity status for interval orders still remains unknown. Here we present a heuristic that, given an interval order P, generates a linear extension , whose jump number is less than 3/2 times the jump number of P.This work was supported by the Deutsche Forschungsgemeinschaft (DFG).     

Topological duality for Tarski algebras

In this paper we will generalize the representation theory developed for finite Tarski algebras given in [7]. We will introduce the notion of Tarski space as a generalization of the notion of dense Tarski set, and we will prove that the category of Tarski algebras with semi-homomorphisms is dually equivalent to the category of Tarski spaces with certain closed relations, called T-relations. By these results we will obtain that the algebraic category of Tarski algebras is dually equivalent to the category of Tarski spaces with certain partial functions. We will apply these results to give a topological characterization of the subalgebras. Received August 21, 2005; accepted in final form December 5, 2006.     

Angle orders

A finite poset is an angle order if its points can be mapped into angular regions in the plane so thatx precedesy in the poset precisely when the region forx is properly included in the region fory. We show that all posets of dimension four or less are angle orders, all interval orders are angle orders, and that some angle orders must have an angular region less than 180° (or more than 180°). The latter result is used to prove that there are posets that are not angle orders.The smallest verified poset that is not an angle order has 198 points. We suspect that the minimum is around 30 points. Other open problems are noted, including whether there are dimension-5 posets that are not angle orders.Research supported in part by the National Science Foundation, grant number DMS-8401281.     

Transforming binary sequences using priority queues

A priority queue transforms an input sequence into an output sequence which is a re-ordering of the sequence . The setR of all such related pairs is studied in the case that is a binary sequence. It is proved thatR is a partial order and that ¦R¦=c _n+1, the (n+1)th Catalan number. An efficient (O(n ²)) algorithm is given for computing the number of outputs achievable from a given input.     

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.     

N-free orders and minimal interval extensions

We investigate problems related to the set of minimal interval extensions of N-free orders. This leads us to a correspondence between this set for an arbitrary order and a certain set of its maximal N-free reductions. We also get a 1-1-correspondence between the set of linear extensions of an arbitrary order and the set of minimal interval extensions of the linegraph of that order. This has an algorithmic consequence, namely the problem of counting minimal interval extensions of an N-free order is #P-complete. Finally a characterization of all N-free orders with isomorphic root graph is given in terms of their lattice of maximal antichains; the lattices are isomorphic iff the root graphs agree.This work was supported by the PROCOPE Program. The first author is supported by the DFG.     

The Stone-Čech compactification of a partial frame via ideals and cozero elements

A partial frame is a meet-semilattice in which certain designated subsets are required to have joins, and finite meets distribute over these. The designated subsets are specified by means of a so-called selection function, denoted by S ; these partial frames are called S-frames.

We construct free frames over S-frames using appropriate ideals, called S-ideals. Taking S-ideals gives a functor from S-frames to frames. Coupled with the functor from frames to S-frames that takes S-Lindelöf elements, it provides a category equivalence between S-frames and a non-full subcategory of frames. In the setting of complete regularity, we provide the functor taking S-cozero elements which is right adjoint to the functor taking S-ideals. This adjunction restricts to an equivalence of the category of completely regular S-frames and a full subcategory of completely regular frames. As an application of the latter equivalence, we construct the Stone-? ech compactification of a completely regular S-frame, that is, its compact coreflection in the category of completely regular S-frames.

A distinguishing feature of the study of partial frames is that a small collection of axioms of an elementary nature allows one to do much that is traditional at the level of frames or locales and of uniform or nearness frames. The axioms are sufficiently general to include as examples of partial frames bounded distributive lattices, σ-frames, κ-frames and frames.