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.     

On some new types of greedy chains and greedy linear extensions of partially ordered sets

Two new types of greedy chains, strongly and semi-strongly greedy, in posets are defined and their role in solving the jump number problem is discussed in this paper. If a poset P contains a strongly greedy chain C then C may be taken as the first chain in an optimal linear extension of P. If a poset P has no strongly greedy chains then it contains an optimal linear extension which starts with a semi-strongly greedy chain. Hence, every poset has an optimal linear extension which consists of strongly and semi-strongly greedy chains. Algorithmic issues of finding such linear extensions are discussed elsewhere (Syslo, 1987, 1988), where we provide a very efficient method for solving the jump number problem which is polynomial in the class of posets whose arc representations contain a bounded number of dummy arcs. In another work, the author has recently demonstrated that this method restricted to interval orders gives rise to 3/2-approximation algorithm for such posets.     

N-free posets as generalizations of series-parallel posets

N-Free posets have recently taken some importance and motivated many studies. This class of posets introduced by Grillet [8] and Heuchenne [11] are very related to another important class of posets, namely the series-parallel posets, introduced by Lawler [12] and studied by Valdes et al. [21]. This paper shows how N-free posets can be considered as generalizations of series-parallel posets, by giving a recursive construction of N-free posets. Furthermore we propose a linear time algorithm to recognize and decompose any N-free poset. This yields some very naturel problems, namely: which are the properties(such as linear time algorithm for some invariant) of series-parallel posets that are kept for N-free posets?     

Jump number problem: The role of matroids

Let L=x ₁ x ₂...x _n be a linear extension of a poset P. Each pair (x _i , x _i+1) such that x _i x _i+1in P is called a jump of L. It is well known that for N-free posets a natural greedy procedure constructing linear extensions yields a linear extension with a minimum number of jumps. We show that there is a matroid corresponding to any N-free poset and apply the Rado-Edmonds Theorem to obtain another proof of this result.     

A recurrence for linear extensions

The number e(P) of linear extensions of a finite poset P is expressed in terms of e(Q) for certain smaller posets Q. The proof is based on M. Schützengerger's concept of promotions of linear extensions.Partially supported by NSF Grant #DMS-8700995.Partially supported by NSF Grant #DMS-8401376.     

A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

Let L=u ₁ , u ₂ , ..., u _k be a linear extension of a poset P. Each pair (u _i , u _i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.     

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 permutahedron ofN-sparse posets

The permutahedron of a poset is the convex hull of all incidence vectors of linear extensions. For the case ofN-sparse posets in which any five elements induce at most oneN we give a characterization of the permutahedron in terms of linear inequalities. This yields an LP-solution for minimizing the weighted mean completion time for jobs with unit processing times andN-sparse precedence constraints. We close with an extension of our approach to arbitrary processing times.     

Edge ranking and searching in partial orders

We consider a problem of searching an element in a partially ordered set (poset). The goal is to find a search strategy which minimizes the number of comparisons. Ben-Asher, Farchi and Newman considered a special case where the partial order has the maximum element and the Hasse diagram is a tree (tree-like posets) and they gave an O(n⁴log³n)-time algorithm for finding an optimal search strategy for such a partial order. We show that this problem is equivalent to finding edge ranking of a simple tree corresponding to the Hasse diagram, which implies the existence of a linear-time algorithm for this problem.Then we study a more general problem, namely searching in any partial order with maximum element. We prove that such a generalization is hard, and we give an -approximate polynomial-time algorithm for this problem.     

Modular posets and semigroups

Posets and poset homomorphisms (preserving both order and parallelism) have been shown to form a category which is equivalent to the category of pogroupoids and their homomorphisms. Among the posets those posets whose associated pogroupoids are semigroups are identified as being precisely those posets which are (C ₂+1)-free. In the case of lattices this condition means that the lattice is alsoN ₅-free and hence modular. Using the standard connection: semigroup to poset to pogroupoid, it is observed that in many cases the image pogroupoid obtained is a semigroup even if quite different from the original one. The nature of this mapping appears intriguing in the poset setting and may well be so seen from the semigroup theory viewpoint.     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Posets with the Maximal Antichain Property

A finite poset F has the maximal antichain property if every maximal F-free subposet of every finite poset P contains a maximal antichain of P. We find all finite posets with the maximal antichain property.     

Resolutions of letterplace ideals of posets

We investigate resolutions of letterplace ideals of posets. We develop topological results to compute their multigraded Betti numbers, and to give structural results on these Betti numbers. If the poset is a union of no more than c chains, we show that the Betti numbers may be computed from simplicial complexes of no more than c vertices. We also give a recursive procedure to compute the Betti diagrams when the Hasse diagram of P has tree structure.     

Irreducible posets with large height exist

The dimension of a poset (X, P) is the minimum number of linear extensions of P whose intersection is P. A poset is irreducible if the removal of any point lowers the dimension. If A is an antichain in X and X ? A ≠ Ø, then dim X ≤ 2 width ((X ? A) + 1. We construct examples to show that this inequality is best possible; these examples prove the existence of irreducible posets of arbitrarily large height. Although many infinite families of irreducible posets are known, no explicity constructed irreducible poset of height larger than four has been found.     

Looping of the numbers game and the alcoved hypercube

We study the so-called looping case of Mozes?s game of numbers, which concerns the (finite) orbits in the reflection representation of affine Weyl groups situated on the boundary of the Tits cone. We give a simple proof that all configurations in the orbit are obtainable from each other by playing the numbers game, and give a strategy for going from one configuration to another. This strategy gives rise to a partition of the finite Weyl group into finitely many graded posets, one for each extending vertex of the associated extended Dynkin diagram. These posets are self-dual and mutually isomorphic, and their Hasse diagrams are dual to the triangulation of the unit hypercube by reflecting hyperplanes. Unlike the weak and Bruhat orders, the top degree is cubic in the number of vertices of the graph. We explicitly compute the rank generating function of the poset.     

A self paired Hopf algebra on double posets and a Littlewood-Richardson rule

Let D be the set of isomorphism types of finite double partially ordered sets, that is sets endowed with two partial orders. On ZD we define a product and a coproduct, together with an internal product, that is, degree-preserving. With these operations ZD is a Hopf algebra. We define a symmetric bilinear form on this Hopf algebra: it counts the number of pictures (in the sense of Zelevinsky) between two double posets. This form is a Hopf pairing, which means that product and coproduct are adjoint each to another. The product and coproduct correspond respectively to disjoint union of posets and to a natural decomposition of a poset into order ideals. Restricting to special double posets (meaning that the second order is total), we obtain a notion equivalent to Stanley's labelled posets, and a Hopf subalgebra already considered by Blessenohl and Schocker. The mapping which maps each double poset onto the sum of the linear extensions of its first order, identified via its second (total) order with permutations, is a Hopf algebra homomorphism, which is isometric and preserves the internal product, onto the Hopf algebra of permutations, previously considered by the two authors. Finally, the scalar product between any special double poset and double posets naturally associated to integer partitions is described by an extension of the Littlewood-Richardson rule.     

The total linear discrepancy of an ordered set

In this paper we introduce the notion of the total linear discrepancy of a poset as a way of measuring the fairness of linear extensions. If L is a linear extension of a poset P, and x,y is an incomparable pair in P, the height difference between x and y in L is |L(x)−L(y)|. The total linear discrepancy of P in L is the sum over all incomparable pairs of these height differences. The total linear discrepancy of P is the minimum of this sum taken over all linear extensions L of P. While the problem of computing the (ordinary) linear discrepancy of a poset is NP-complete, the total linear discrepancy can be computed in polynomial time. Indeed, in this paper, we characterize those linear extensions that are optimal for total linear discrepancy. The characterization provides an easy way to count the number of optimal linear extensions.     

3-Interval irreducible partially ordered sets

In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posets due to Trotter [9].We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformationP B(P), such that IdimP=dimB(P). This transformation has been introduced in [2].Supported by the DFG under grant FE 340/2–1.     

The Involutory Dimension of Involution Posets

The involutory dimension, if it exists, of an involution poset P:=(P,,) is the minimum cardinality of a family of linear extensions of , involutory with respect to , whose intersection is the ordering . We show that the involutory dimension of an involution poset exists iff any pair of isotropic elements are orthogonal. Some characterizations of the involutory dimension of such posets are given. We study prime order ideals in involution posets and use them to generate involutory linear extensions of the partial ordering on orthoposets. We prove several of the standard results in the theory of the order dimension of posets for the involutory dimension of involution posets. For example, we show that the involutory dimension of a finite orthoposet does not exceed the cardinality of an antichain of maximal cardinality. We illustrate the fact that the order dimension of an orthoposet may be different from the involutory dimension.