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.     

Level Eulerian Posets

The notion of level posets is introduced. This class of infinite posets has the property that between every two adjacent ranks the same bipartite graph occurs. When the adjacency matrix is indecomposable, we determine the length of the longest interval one needs to check to verify Eulerianness. Furthermore, we show that every level Eulerian poset associated to an indecomposable matrix has even order. A condition for verifying shellability is introduced and is automated using the algebra of walks. Applying the Skolem–Mahler–Lech theorem, the ab-series of a level poset is shown to be a rational generating function in the non-commutative variables a and b. In the case the poset is also Eulerian, the analogous result holds for the cd-series. Using coalgebraic techniques a method is developed to recognize the cd-series matrix of a level Eulerian poset.     

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.     

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.     

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.     

Classification of the factorial functions of Eulerian binomial and Sheffer posets

We give a complete classification of the factorial functions of Eulerian binomial posets. The factorial function B(n) either coincides with n!, the factorial function of the infinite Boolean algebra, or ²n−1, the factorial function of the infinite butterfly poset. We also classify the factorial functions for Eulerian Sheffer posets. An Eulerian Sheffer poset with binomial factorial function B(n)=n! has Sheffer factorial function D(n) identical to that of the infinite Boolean algebra, the infinite Boolean algebra with two new coatoms inserted, or the infinite cubical poset. Moreover, we are able to classify the Sheffer factorial functions of Eulerian Sheffer posets with binomial factorial function B(n)=²n−1 as the doubling of an upside-down tree with ranks 1 and 2 modified. When we impose the further condition that a given Eulerian binomial or Eulerian Sheffer poset is a lattice, this forces the poset to be the infinite Boolean algebra BX or the infinite cubical lattice . We also include several poset constructions that have the same factorial functions as the infinite cubical poset, demonstrating that classifying Eulerian Sheffer posets is a difficult problem.     

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.     

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.     

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.     

A Lattice Path Interpretation of the Diamond Product

The diamond product is the poset operation that when applied to the face lattices of two polytopes results in the face lattice of the Cartesian product of the polytopes. Application of the diamond product to two Eulerian posets is a bilinear operation on the cd-indices of the two posets, yielding a product on cd-polynomials. A lattice path interpretation is provided for this product of two cd-monomials.     

Lim-inf convergence in partially ordered sets

The lim-inf convergence in a complete lattice was introduced by Scott to characterize continuous lattices. Here we introduce and study the lim-inf convergence in a partially ordered set. The main result is that for a poset P the lim-inf convergence is topological if and only if P is a continuous poset. A weaker form of lim-inf convergence in posets is also discussed.     

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?     

On-Line Dimension for Posets Excluding Two Long Incomparable Chains

For a positive integer k, let k?+?k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k?≥?1, there exists a constant c _k so that First Fit will use at most $c_kw^2$ chains in partitioning a poset P of width at most w, provided the poset excludes k?+?k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that O(w ^16logw ) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead’s exponential bound: (5 ^w ???1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek–Krawczyk–Szczypka bound for the performance of First Fit to 8(k???1)² w, which in turn yields the modest improvement to O(w ^14logw ) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t?=?t(k,w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k?+?k as a subposet.     

The poset structures admitting the extended binary Golay code to be a perfect code

Brualdi et al. [Codes with a poset metric, Discrete Math. 147 (1995) 57-72] introduced the concept of poset codes, and gave an example of poset structure which admits the extended binary Golay code to be a 4-error-correcting perfect P-code. In this paper we classify all of the poset structures which admit the extended binary Golay code to be a 4-error-correcting perfect P-code, and show that there are no posets which admit the extended binary Golay code to be a 5-error-correcting perfect P-code.     

Harmonics on posets

Given a finite ranked poset P, for each rank of P a space of complex valued functions on P called harmonics is defined. If the automorphism group G of P is sufficiently rich, these harmonic spaces yield irreducible representations of G. A decomposition theorem, which is analogous to the decomposition theorem for spherical harmonics, is stated. It is also shown that P can always be decomposed into posets whose principal harmonics are orthogonal polynomials. Classical examples are given.     

Dimension of the crown Skn

In 1941, Dushnik and Miller introduced the concept of the dimension of a poset (X, P) as the minimum number of linear extensions of P whose intersection is exactly P. Although Dilworth has given a formula for the dimension of distributive lattices, the general problem of determining the dimension of a poset is quite difficult. An equally difficult problem is to classify those posets which are dimension irreducible, i.e., those posets for which the removal of any point lowers the dimension. In this paper, we construct for each n≥3, k≥0, a poset, called a crown and denoted S^k_n, for which the dimension is given by the formula $\text{2?(n+k)}\text{(k+2)}$. Furthermore, for each t≥3, we show that there are infinitely many crowns which are irreducible and have dimension t. We then demonstrate a method of combining a collection of irreducible crowns to form an irreducible poset whose dimension is the sum of the crowns in the collection. Finally, we construct some infinite crowns possessing combinatorial properties similar to finite crowns.     

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.     

Methods for nesting rank 3 normalized matching rank-unimodal posets

Anderson and Griggs proved independently that a rank-symmetric-unimodal normalized matching (NM) poset possesses a nested chain decomposition (or nesting), and Griggs later conjectured that this result still holds if we remove the condition of rank-symmetry. We give several methods for constructing nestings of rank-unimodal NM posets of rank 3, which together produce substantial progress towards the rank 3 case of the Griggs nesting conjecture. In particular, we show that certain nearly symmetric posets are nested; we show that certain highly asymmetric rank 3 NM posets are nested; and we use results on minimal rank 1 NM posets to show that certain other rank 3 NM posets are nested.     

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.