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.     

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

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.     

A note on random k-dimensional posets

In 2009, Janson [Poset limits and exchangeable random posets, Institut Mittag-Leffler preprint, 36pp, arXiv:0902.0306] extended the recent theory of graph limits to posets, defining convergence for poset sequences and proving that every such sequence has a limit object. In this paper, we focus on k-dimensional poset sequences. This restriction leads to shorter proofs and to a more intuitive limit object. As before, the limit object can be used as a model for random posets, which generalizes the well known random k-dimensional poset model. This investigation also leads to a definition of quasirandomness for k-dimensional posets, which can be captured by a natural distance that measures the discrepancy of a k-dimensional poset.     

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 orbits of order ideals of minuscule posets

An action on order ideals of posets considered by Fon-Der-Flaass is analyzed in the case of posets arising from minuscule representations of complex simple Lie algebras. For these minuscule posets, it is shown that the Fon-Der-Flaass action exhibits the cyclic sieving phenomenon, as defined by Reiner, Stanton, and White. A uniform proof is given by investigation of a bijection due to Stembridge between order ideals of minuscule posets and fully commutative Weyl group elements. This bijection is proven to be equivariant with respect to a conjugate of the Fon-Der-Flaass action and an arbitrary Coxeter element. If P is a minuscule poset, it is shown that the Fon-Der-Flaass action on order ideals of the Cartesian product P×[2] also exhibits the cyclic sieving phenomenon, only the proof is by appeal to the classification of minuscule posets and is not uniform.     

Finite Eulerian posets which are binomial, Sheffer or triangular

In this paper we study finite Eulerian posets which are binomial, Sheffer or triangular. These important classes of posets are related to the theory of generating functions and to geometry. The results of this paper are organized as follows:

•

We completely determine the structure of Eulerian binomial posets and, as a conclusion, we are able to classify factorial functions of Eulerian binomial posets.

•

We give an almost complete classification of factorial functions of Eulerian Sheffer posets by dividing the original question into several cases.

•

In most cases above, we completely determine the structure of Eulerian Sheffer posets, a result stronger than just classifying factorial functions of these Eulerian Sheffer posets.

We also study Eulerian triangular posets. This paper answers questions posed by R. Ehrenborg and M. Readdy. This research is also motivated by the work of R. Stanley about recognizing the boolean lattice by looking at smaller intervals.     

A criterion for polynomial growth of a-free two-peak posets of tame prinjective type *

It is well known from the results of L, A. Nazarova and A. G. Zavadskij [18], [19], see also [25, Chapter 15], that a poset J with one maximal element is of tame prinjective type and of polynomial growth if and only if J does not contain neither any of the Nazarova's hypercritical posets (1,1,1,1,1)^*, (1,1,1,2)^*,(2,2,3)^*, (1,3,4)^*,(W,5)^*,(1,2,6)^* nor the Nazarova-Zavadskij poset (NZ)^* (see Table 1 below). In the present paper we extend this result to a class of posets with two maximal elements. We show that Ã-free poset with two maximal elements is of tame representation type and of polynomial growth if and only if the Tits quadratic form q^s → Z (see (1.7) below) associated with J is weakly non-negative and J does not contain any of the six posets listed in Table 1 as a peak subposet.     

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.     

Continuity of posets via Scott topology and sobrification

In this paper, posets which may not be dcpos are considered. The concept of embedded bases for posets is introduced. Characterizations of continuity of posets in terms of embedded bases and Scott topology are given. The main results are:

(1)

A poset is continuous iff it is an embedded basis for a dcpo up to an isomorphism;

(2)

A poset is continuous iff its Scott topology is completely distributive;

(3)

A topological T₀ space is a continuous poset equipped with the Scott topology in the specialization order iff its topology is completely distributive and coarser than or equal to the Scott topology;

(4)

A topological T₁ space is a discrete space iff its topology is completely distributive.

These results generalize the relevant results obtained by J.D. Lawson for dcpos.     

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.     

From finite posets to chain complete posets having no infinite antichain

LetF denote the class of finite posets and letF ^* denote the larger class of chain complete posets which have no infinite antichain. We show that a variety of results which are known to hold for finite posets are also true for posets inF ^*.This paper was written while the first author was visiting the University of Calgary. Research supported by grants from the National Natural Science Foundation of China, and the National Education Committee of China for returning scholars from abroad.Research supported by NSERC grant #69-0982.     

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.     

Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets

Linear algebra technique in the study of linear representations of finite posets is developed in the paper. A concept of a quadratic wandering on a class of posets I is introduced and finite posets I are studied by means of the four integral bilinear forms (1.1), the associated Coxeter transformations, and the Coxeter polynomials (in connection with bilinear forms of Dynkin diagrams, extended Dynkin diagrams and irreducible root systems are also studied). Bilinear equivalences between some of the forms are established and equivalences with the bilinear forms of Dynkin diagrams and extended Dynkin diagrams are discussed. A homological interpretation of the bilinear forms (1.1) is given and Z-bilinear equivalences between them are discussed. By applying well-known results of Bongartz, Loupias, and Zavadskij-Shkabara, we give several characterisations of posets I, with the Euler form weakly positive (resp. with the reduced Euler form weakly positive), and posets I, with the Tits form weakly positive.     

Towards the reconstruction of posets

The reconstruction conjecture for posets is the following: Every finite posetP of more than three elements is uniquely determined — up to isomorphism — by its collection of (unlabelled) one-element-deleted subposets P–{x}:xV(P).We show that disconnected posets, posets with a least (respectively, greatest) element, series decomposable posets, series-parallel posets and interval orders are reconstructible and that N-free orders are recognizable.We show that the following parameters are reconstructible: the number of minimal (respectively, maximal) elements, the level-structure, the ideal-size sequence of the maximal elements, the ideal-size (respectively, filter-size) sequence of any fixed level of the HASSE-diagram and the number of edges of the HASSE-diagram.This is considered to be a first step towards a proof of the reconstruction conjecture for posets.Research partly supported by DAAD.     

Ramsey property, ultrametric spaces, finite posets, and universal minimal flows

We introduce the class COU _S of finite ultrametric spaces with distances in the set S and with two additional linear orderings. We also introduce the class EOP of finite posets with two additional linear orderings. In this paper, we prove that COU _S and EOP are Ramsey classes. In addition, we give an application of our results to calculus of universal minimal flows.     

Strongly continuous posets and the local Scott topology

In this paper, the concept of strongly continuous posets (SC-posets, for short) is introduced. A new intrinsic topology—the local Scott topology is defined and used to characterize SC-posets and weak monotone convergence spaces. Four notions of continuity on posets are compared in detail and some subtle counterexamples are constructed. Main results are: (1) A poset is an SC-poset iff its local Scott topology is equal to its Scott topology and is completely distributive iff it is a continuous precup; (2) For precups, PI-continuity, LC-continuity, SC-continuity and the usual continuity are equal, whereas they are mutually different for general posets; (3) A T₀-space is an SC-poset equipped with the Scott topology iff the space is a weak monotone convergence space with a completely distributive topology contained in the local Scott topology of the specialization order.     

On Lattices Embeddable into Lattices of Order-Convex Sets. II Star-like Posets

We find a syntactic characterization of the class \(\mathrm{\mathbf{SUB}}(\mathcal{S})\cap\mathrm{Fin}\) of finite lattices embeddable into convexity lattices of a certain class of posets which we call star-like posets and which is a proper subclass in the class of N-free posets. The characterization implies that the class \(\mathrm{\mathbf{SUB}}(\mathcal{S})\cap\mathrm{Fin}\) forms a pseudovariety.     

The rank-generating functions of upho posets

Upper homogeneous finite type (upho) posets are a large class of partially ordered sets with the property that the principal order filter at every vertex is isomorphic to the whole poset. Well-known examples include k-ary trees, the grid graphs, and the Stern poset. Very little is known about upho posets in general. In this paper, we construct upho posets with Schur-positive Ehrenborg quasisymmetric functions, whose rank-generating functions have rational poles and zeros. We also categorize the rank-generating functions of all planar upho posets. Finally, we prove the existence of an upho poset with an uncomputable rank-generating function.