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.     

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.     

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.     

Balance theorems for height-2 posets

We prove that every height-2 finite poset with three or more points has an incomparable pair {x, y} such that the proportion of all linear extensions of the poset in which x is less than y is between 1/3 and 2/3. A related result of Komlós says that the containment interval [1/3, 2/3] shrinks to [1/2, 1/2] in the limit as the width of height-2 posets becomes large. We conjecture that a poset denoted by V _m ⁺ maximizes the containment interval for height-2 posets of width m+1.     

Linear extension majority cycles in height-1 orders

For points x and y in a poset (X, >) let x> _p y mean that more linear extensions of the poset have x above y than y above x. It has been known for some time that > _p can have cycles when the height of the poset is two or more. Moreover, the smallest posets with a > _p cycle have nine points and heights of 2, 3 and 4. We show here that height-1 posets can also have > _p cycles. Our smallest example for this phenomenon has 15 points.Research supported through a fellowship from the Center for Advanced Study of the University of Delaware.     

Order series of labelled posets

Order series of labelled posets are multi-analogues of the more familiar order polynomials; the corresponding multi-analogues of the related representation polynomials are calledE-series. These series can be used to describe the effect of composition of labelled posets on their order polynomials, whence their interest for us. We give a reciprocity theorem forE-series, and show that for an unlabelled poset the form of theE-series depends only upon the comparability graph of the poset. We also prove that theE-series of any labelled poset is a rational power series (in many indeterminates) and give an algorithm for computing it which runs in polynomial time when the poset is strictly labelled and of bounded width. Finally, we give an explicit product formula for theE-series of strictly labelled interval posets.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant #0105392.     

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.     

A solution to a spectral poset problem of Lewis and Ohm

We show that there is a 1-dimensional (countable) non-spectral poset X such that for all x≠y∈X, ↑x∩↑y and ↓x∩↓y are finite subsets. On the other hand, we obtain some sufficient conditions for posets to be spectral.     

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.     

How To Split Antichains In Infinite Posets*

A maximal antichain A of poset P splits if and only if there is a set B ⊂ A such that for each p ∈ P either b ≤ p for some b ∈ B or p ≤ c for some c ∈ A\B. The poset P is cut-free if and only if there are no x < y < z in P such that [x,z]_P = [x,y]_P ∪ [y,z]_P . By [1] every maximal antichain in a finite cut-free poset splits. Although this statement for infinite posets fails (see [2])) we prove here that if a maximal antichain in a cut-free poset “resembles” to a finite set then it splits. We also show that a version of this theorem is just equivalent to Axiom of Choice. We also investigate possible strengthening of the statements that “A does not split” and we could find a maximal strengthening. * This work was supported, in part, by Hungarian NSF, under contract Nos. T37846, T34702, T37758, AT 048 826, NK 62321. The second author was also supported by Bolyai Grant.     

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.     

A note on merging

For a finite poset P and x, yP let pr(x>y) be the fraction of linear extensions which put x above y. N. Linial has shown that for posets of width 2 there is always a pair x, y with 1/3 pr(x>y)2/3. The disjoint union C ₁C ₂ of a 1-element chain with a 2-element chain shows that the bound 1/3 cannot be further increased. In this paper the extreme case is characterized: If P is a poset of width 2 then the bound 1/3 is exact iff P is an ordinal sum of C ₁C ₂'s and C ₁'s.     

A family of (n−1)! Diagonal polynomial orders ofN n

Letn>0 be an element of the setN of nonnegative integers, and lets(x)=x ₁+...+x _n , forx=(x ₁, ...,x _n ) N _n . Adiagonal polynomial order inN _n is a bijective polynomialp:N _n N (with real coefficients) such that, for allx,y N _n ,p(x)<p(y) whenevers(x)<s(y). Two diagonal polynomial orders areequivalent if a relabeling of variables makes them identical. For eachn, Skolem (1937) found a diagonal polynomial order. Later, Morales and Lew (1992) generalized this polynomial order, obtaining a family of 2 ^n–2 (n>1) inequivalent diagonal polynomial orders. Here we present, for eachn>0, a family of (n – 1)! diagonal polynomial orders, up to equivalence, which contains the Morales and Lew diagonal orders.     

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.     

A structure theorem for posets admitting a “strong” chain partition:: A generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities)

Suppose a finite poset P is partitioned into three non-empty chains so that, whenever p, q∈P lie in distinct chains and p<q, then every other element of P is either above p or below q.In 1985, the following conjecture was made by David Daykin and Jacqueline Daykin: such a poset may be decomposed into an ordinal sum of posets such that, for 1?i?n, one of the following occurs:

(1)

R_i is disjoint from one of the chains of the partition; or

(2)

if p, q∈R_i are in distinct chains, then they are incomparable.

The conjecture is related to a question of R. L. Graham's concerning probability correlation inequalities for linear extensions of finite posets.In 1996, a proof of the Daykin-Daykin conjecture was announced (by two other mathematicians), but their proof needs to be rectified.In this note, a generalization of the conjecture is proven that applies to finite or infinite posets partitioned into a (possibly infinite) number of chains with the same property. In particular, it is shown that a poset admits such a partition if and only if it is an ordinal sum of posets, each of which is either a width 2 poset or else a disjoint sum of chains. A forbidden subposet characterization of these partial orders is also obtained.     

Order varieties generated by finite posets

In a 1981 paper, Duffus and Rival define an order variety as a class of posets that is closed under the formation of products and retracts. They also introduce the notion of an irreducible poset. In the present paper we define nonextendible colored posets and certain minimal nonextendible colored posets that we call zigzags. We characterize via nonextendible colored posets the order varieties generated by a set of posets. If the generating set contains only finite posets our characterization is via zigzags. By using these theorems we give a characterization of finite irreducible posets.As an application we show that two different finite irreducible posets generate two different order varieties. We also show that there is a poset which has two different representations by irreducible posets. We thereby settle two open problems listed in the Duffus and Rival paper.     

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.     

Substitution and atomic extension on greedy posets

In this paper, we study the operations of substitution and atomic extension on greedy posets. For the substitution operation, if P=(P ₁ , x, P ₂ )is a greedy poset, then P ₁ and P ₂ are greedy posets, the converse being false. However, for the atomic extension, P=P ₁ (x, P ₂ )is a greedy poset if and only if P ₁ and P ₂ are greedy posets. We prove also that the class of greedy semi-partitive lattices is the smallest one containing M _n (n2), B ₃ and closed by atomic extension. The class C _n of greedy posets with jump number n is infinite. However, we show that C _n can be obtained, in a very simple way, from a subclass D _n of finite cardinal ity. We construct D _n for n=1, 2.     

Path-Connected Partially Ordered Sets

The graph of a partially ordered set (X, ?) has X as its set of vertices and (x,y) is an edge if and only if x covers y or y covers x. The poset is path-connected if its graph is connected. Two integer-valued metrics, distance and fence, are defined for path-connected posets. Together the values of these metrics determine a path-connected poset to within isomorphism and duality. The result holds for path-connected preordered sets where distance and fence are pseudometrics. The result fails for non-path-connected posets.