The jump number of Z-free ordered sets

An ordered set P is called Z-free if it does not contain a four-element subset {a, b, c, d} such that a and c are the only comparabilities among these elements. In this paper we present a polynomial algorithm to find the jump number of finite Z-free ordered sets and that of their duals.     

Minimizing bumps in linear extensions of ordered sets

A linear extension x ₁ x ₂ x ₃ ... of a partially ordered set (X, <) has a bump whenever x _i <x _i +1. We examine the problem of determining linear extensions with as few bumps as possible. Heuristic algorithms for approximate bump minimization are considered.     

On the size of jump-critical ordered sets

The maximum size of a jump-critical ordered set with jump-number m is at most (m+1)!     

Automorphisms and isotone self-maps of ordered sets with top and bottom

For an ordered setP letP ^P denote the set of all isotone self-maps on P, that is, all mapsf fromP toP such thatxy impliesf(x)f(y), and let Aut (P) the set of all automorphisms onP, that is, all bijective isotone self-maps inP ^P . We establish an inequality relating ¦P ^P ¦ and ¦Aut(P)¦ in terms of the irreducibles ofP. As a straightforward corollary, we show that Rival and Rutkowski's automorphism conjecture is true for lattices. It is also true for ordered sets with top and bottom whose covering graphs are planar.Supported in part by NSERC (Grant no. A2507).Supported under an NSERC International Research Fellowship.     

A theory of recursive dimension for ordered sets

The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172.     

Nonstandard analysis of ordered sets

We introduce a nonstandard approach to the study of ordered setsX based on a classification of the elements of the ordered set *X into three types, upward, downward, and lateral, which may be thought of dynamically as arising from the possibilities of upward, downward, and lateral motion withinX. Initial applications include the characterization thatX has no infinite diverse subset iff *X has no lateral elements, a result subsequently exploited in work on the interval topology and order-compatibility, where we give a nonstandard proof of Naito's result that ifX has no infinite diverse subset, it has a unique order-compatible topology. We also describe how the completion of a nonempty linearly ordered setX may be obtained as a quotient of *X.     

Representations of finite partially ordered sets over commutative artinian uniserial rings

Categories of representations of finite partially ordered sets over commutative artinian uniserial rings arise naturally from categories of lattices over orders and abelian groups. By a series of functorial reductions and a combinatorial analysis, the representation type of a category of representations of a finite partially ordered set S over a commutative artinian uniserial ring R is characterized in terms of S and the index of nilpotency of the Jacobson radical of R. These reductions induce isomorphisms of Auslander-Reiten quivers and preserve and reflect Auslander-Reiten sequences. Included, as an application, is the completion of a partial characterization of representation type of a category of representations arising from pairs of finite rank completely decomposable abelian groups.     

On complete partially ordered sets and compatible topologies

We describe two complete partially ordered sets which are the intersection of complete linear orderings but which have no compatible Hausdorff topology. One is two-dimensional, while the second is countable, and leads to an example of a countable, compact, T ₁ space with a countable base which is not the continuous image of any compact Hausdorff space.     

Free generating sets of lattice-ordered abelian groups

We prove that the generators g₁,…,g_n of a lattice-ordered abelian group G form a free generating set iff each ?-ideal generated by any n−1 linear combinations of the g_i is strictly contained in some maximal ?-ideal of G.     

Minimizing setups in ordered sets of fixed width

A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.     

Forbidden retracts for finite ordered sets of width at most four

The relationship between the fixed point property and forbidden retracts associated with a forgetful functor is formulated. Finite ordered sets of width at most four with fixed point free automorphisms are described. Linear time algorithms for deciding whether a finite ordered set of width two has the fixed point property and whether a finite ordered set of width at most three has a fixed point free automorphism are presented.     

A cofinal coloring theorem for partially ordered algebras

If P is a directed partially ordered algebra of an appropriate sort-e.g. an upper semilattice-and has no maximal element, then P has two disjoint subalgebras each cofinal in P. In fact, if P has cofinality then there exists a family of such disjoint subalgebras. A version of this result is also proved without the directedness assumption, in which the cofinality of P is replaced by an invariant which we call its global cofinality.This work was done while the first author was partly supported by NSF contract MCS 82-02632.     

The normal subgroup lattice of 2-transitive automorphism groups of linearly ordered sets

Using combinatorial and model-theoretic means, we examine the structure of normal subgroup lattices N(A()) of 2-transitive automorphism groups A() of infinite linearly ordered sets (, ). Certain natural sublattices of N(A()) are shown to be Stone algebras, and several first order properties of their dense and dually dense elements are characterized within the Dedekind-completion of (, ). As a consequence, A() has either precisely 5 or at least 2²¹ (even maximal) normal subgroups, and various other group- and lattice-theoretic results follow.     

Quotients of peck posets

An elementary, self-contained proof of a result of Pouzet and Rosenberg and of Harper is given. This result states that the quotient of certain posets (called unitary Peck) by a finite group of automorphisms retains some nice properties, including the Sperner property. Examples of unitary Peck posets are given, and the techniques developed here are used to prove a result of Lovász on the edge-reconstruction conjecture.Supported in part by a National Science Foundation research grant.     

Finite projective ordered sets

We show that quasiprojectivity and projectivity are equivalent properties for finite ordered sets of more than two elements.     

Universally generic finitely generated ordered Abelian groups

It is shown that a finitely generated ordered Abelian group is generic if and only if it is superdiscrete, i.e., each homomorphic image is discretely ordered. The forcing concept uses universal sentences as forcing conditions.     

A partition relation for partially ordered sets

We introduce a partition relation which is an alternate for measuring how badly the ordinary partition relation fails, we develop its corresponding partition calculus and we determine its status for various typical partially ordered sets.     

Ladders in ordered sets

An ordered set P is said to have the 2-cutset property if for every element x of P there is a subset S of P whose elements are noncomparable to x, such that |S|2 and such that every maximal chain in P meets {x}S. It is shown that if P has the 2-cutset property and has width n then P contains a ladder of length [1/2(n–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.