Antichain sequences

For any finite partially ordered set S we display a dual transportation system of linear inequalities, and a bijection A(x) from the maximal integer-valued solutions x of this system onto the maximal sequences of k antichains in S. This provides a simple translation to a dual transportation problem of the problem: find a maximum weight union of k antichains.Research supported by the Natural Sciences and Engineering Research of Canada.     

Finite cutsets and finite antichains

An ordered set (P,) has the m cutset property if for each x there is a set Fx with cardinality less than m, such that each element of Fx is incomparable to x and {x} Fx meets every maximal chain of (P,). Let n be least, such that each element x of any P having the m cutset property belongs to some maximal antichain of cardinality less than n. We specify n for m < w. Indeed, n-1=m= width P for m=1,2,n=5 if m=3 and n₁ if m 4. With the added hypothesis that every bounded chain has a supremum and infimum in P, it is shown that for 4m₀, n=₀. That is, if each element x has a finite cutset Fx, each element belongs to a finite maximal antichain.This work was supported by the NSERC of Canada.     

The PT-order,minimal cutsets and menger property

If P is a poset, the associated PT-order is the quasi order in which a b holds if every maximal chain of P which passes through a also passes through b. P is special if whenever A is a chain in P and a=sup A or inf A, then there is b A such that b a. It is proved that if P is chain complete and special then the set of -maximal elements is -dominating and contains a minimal cutset. As corollaries of this, we give partial answers to (i) a question of Rival and Zaguia by showing that if P is regular and special every element is in a minimal cutset and (ii) a question of Brochet and Pouzet by showing that if P is chain complete and special then it has the Menger property.Research partially supported by grants from the National Natural Science Foundation of China and the Natural Science Foundation of Shaanxi province     

Minimum cutsets for an element of a boolean lattice

An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B _n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B _n. A new result that is provided by this approach is a list of all minimum cutsets for A.Research supported in part by NSF Grant DMS 87-01475.Research supported in part by NSF Grant DMS 86-06225 and Air Force OSR-86-0076.     

Maximal chains and cutsets of an ordered set: A menger type approach

We prove the following results which are related to Menger's theorem for (infinite) ordered sets. (i) If the space of maximal chains of an ordered set is compact, then the maximum number of pairwise disjoint maximal chains is finite and is equal to the minimum size of a cutset, (i.e. a set which meets all maximal chains). (ii) If the maximal chains pairwise intersect, then the intersection of finitely many is never empty. One corollary of (ii) is that, if the maximal chains pairwise intersect and if one of the maximal chains is complete, then there is an element common to all maximal chains.     

Crowns,cutsets, and valuable partial orders

We consider the problem of recognizing those partial orders which admit a valuation: this is a linear-algebraic condition which arises naturally in an algebraic/geometric context. We show that a partial order has at most one valuation (which is integer-valued) and present various structural conditions which are either necessary or sufficient for a partial order to be valuable. The first main result is a reduction theorem which allows us to restrict attention to those partial orders which do not have a bounded cutset. We use this and a theorem of Kelly and Rival to prove the second main result: that every contraction of a bounded partial order is fibre-valuable if and only if the partial order is a dismantlable lattice. This result has a geometric interpretation.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.     

Posets isomorphic to their extensions

A standard extension for a poset P is a system Q of lower ends (descending subsets) of P containing all principal ideals of P. An isomorphism between P and Q is called recycling if [Y]Q for all YQ. The existence of such an isomorphism has rather restrictive consequences for the system Q in question. For example, if Q contains all lower ends generated by chains then a recycling isomorphism between P and Q forces Q to be precisely the system of all principal ideals. For certain standard extensions Q, it turns out that every isomorphism between P and Q (if there is any) must be recycling. Our results include the well-known fact that a poset cannot be isomorphic to the system of all lower ends, as well as the fact that a poset is isomorphic to the system of all ideals (i.e., directed lower ends) only if every ideal is principal.     

Balancing pairs and the cross product conjecture

In a finite partially ordered set, Prob (x>y) denotes the proportion of linear extensions in which elementx appears above elementy. In 1969, S. S. Kislitsyn conjectured that in every finite poset which is not a chain, there exists a pair (x,y) for which 1/3Prob(x>y)2/3. In 1984, J. Kahn and M. Saks showed that there exists a pair (x,y) with 3/11x>y)<8/11, but the full 1/3–2/3 conjecture remains open and has been listed among ORDER's featured unsolved problems for more than 10 years.In this paper, we show that there exists a pair (x,y) for which (5–5)/10Prob(x>y)(5+5)/10. The proof depends on an application of the Ahlswede-Daykin inequality to prove a special case of a conjecture which we call the Cross Product Conjecture. Our proof also requires the full force of the Kahn-Saks approach — in particular, it requires the Alexandrov-Fenchel inequalities for mixed volumes.We extend our result on balancing pairs to a class of countably infinite partially ordered sets where the 1/3–2/3 conjecture isfalse, and our bound is best possible. Finally, we obtain improved bounds for the time required to sort using comparisons in the presence of partial information.An extended abstract of an earlier version of this paper appears as [6]. The results here are much stronger than in [6], and this paper has been written so as to overlap as little as possible with that version.     

How small can a lattice of order-dimension n be?

The aim of this paper is to study the order-dimension of partition lattices and linear lattices. Our investigations were motivated by a question due to Bill Sands: For a lattice L, does dim L=n always imply |L|≥2 ⁿ ? We will answer this question in the negative since both classes of lattices mentioned above form counterexamples. In the case of the partition lattices, we will determine the dimension up to an absolute constant. For the linear lattice over GF(2), L _n , we determine the dimension up to a factor C/n for an absolute constant C.     

Ordered sets with no chains of ideals of a given type

We study the possible order types of chains of ideals in an ordered set. Our main result is this. Given an indecomposable countable order type , there is a finite listA ₁ , ...,A _n of ordered sets such that for every ordered setP the setJ(P) of ideals ofP, ordered by inclusion, contains a chain of type if and only ifP contains a subset isomorphic to one of theA ₁ ^#x03B1; , ...,A _n . The finiteness of the list relies on the notion of better quasi-ordering introduced by Nash-Williams and the properties of scattered chains obtained by Laver.The results presented. here constitute the second chapter of the third cycle thesis presented by the second author before the Claude Bernard University, Lyon (July 1983).     

Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x ₁<x ₂<...<x _m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0i<m, choose x _i+1 as a minimal element of P–{x _j :ji}. A linear extension is said to be greedy, if we also require that x _i+1 covers x _i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P–A|2, we show that the greedy dimension of P does not exceed |P–A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|4. If the width of P–A is n and n2, we show that the greedy dimension of P does not exceed n ²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n–1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.Research supported in part by the National Science Foundation under ISP-80110451.Research supported in part by the National Science Foundation under ISP-80110451 and DMS-8401281.     

Dimension versus size

We investigate the behavior of f(d), the least size of a lattice of order dimension d. In particular we show that the lattice of a projective plane of order n has dimension at least n/ln(n), so that f(d)=O(d) ² log² d. We conjecture f(d)=(d ² ), and prove something close to this for height-3 lattices, but in general we do not even know whether f(d)/d.Supported in part by NSF grant MCS 83-01867, AFORS grant number 0271 and a Sloan Research Fellowship.     

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.     

The fixed point property in ordered sets of width two

We consider the fixed point property (FPP) in an ordered set of width two (every antichain contains at most two elements). The necessary condition of the FPP and a number of equivalent conditions to the FPP in such sets is established. The product theorem is proved, as well.     

Comparability invariance of the fixed point property

We show that the fixed point property is comparability invariant for finite ordered sets; that is, if P and Q are finite ordered sets with isomorphic comparability graphs, then P has the fixed point property if and only if Q does. In the process we give a characterization of comparability invariants which can also be used to give shorter proofs of some known results.     

A short proof that N 3 is not a circle containment order

A partially ordered set P is called a circle containment order provided one can assign to each xP a circle C _x so that . We show that the infinite three-dimensional poset N ³ is not a circle containment order and note that it is still unknown whether or not [n]³ is such an order for arbitrarily large n.     

Ordered sets with small width and large jump number

The following result is proved in this note: For any positive integers w and t, if an ordered set P has jump number at least (t+1) ^w–1, then either the width of P is more than w, or P has a tower, i.e., a linear sum of pairs of noncomparable elements, of height more than t.     

Crooked diagrams with few slopes

A natural and practical criterion in the preparation of diagrams of ordered sets is to minimize the number of different slopes used for the edges. For any diagram this is at least the maximum number of upper covers and of lower covers of any element. While this maximum degree is not always enough we show that it is as long as any edge joining a covering pair may be bent, to produce a crooked diagram.     

III-Homomorphisms and III-congruences on posets

A new homomorphism between two partially ordered sets (the III-homomorphism) and a new congruence on a poset (the III-congruence) are introduced. Some properties of these homomorphisms and congruences and their relationship to the other known homomorphisms and congruences on posets are investigated. In contrast to total algebras, there are many different ways to introduce these notions. It is usually required that the respective notions should coincide with the usual definitions whenever lattices or semilattices are treated. The present paper presents an approach which in some sense completes the hierarchy of definitions so far used.     

Semiorders and the 1/3–2/3 conjecture

A well-known conjecture of Fredman is that, for every finite partially ordered set (X, <) which is not a chain, there is a pair of elements x, y such that P(x, the proportion of linear extensions of (X, <) with x below y, lies between 1/3 and 2/3. In this paper, we prove the conjecture in the special case when (X, <) is a semiorder. A property we call 2-separation appears to be crucial, and we classify all locally finite 2-separated posets of bounded width.