Möbius Polynomials of Face Posets of Convex Polytopes

The Möbius polynomial is an invariant of ranked posets, closely related to the Möbius function. In this paper, we study the Möbius polynomial of face posets of convex polytopes. We present formulas for computing the Möbius polynomial of the face poset of a pyramid or a prism over an existing polytope, or of the gluing of two or more polytopes in terms of the Möbius polynomials of the original polytopes. We also present general formulas for calculating Möbius polynomials of face posets of simplicial polytopes and of Eulerian posets in terms of their f-vectors and some additional constraints.     

Rank polynomials of fence posets are unimodal

We prove a conjecture of Morier-Genoud and Ovsienko that says that rank polynomials of the distributive lattices of lower ideals of fence posets are unimodal. We do this by proving a stronger version of the conjecture due to McConville, Sagan, and Smyth. Our proof involves introducing a related class of posets, which we call circular fence posets and showing that their rank polynomials are symmetric. We also apply the recent work of Elizalde, Plante, Roby, and Sagan on rowmotion on fences and show many of their homomesy results hold for the circular case as well.     

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.     

Coproducts and the cd-Index

The linear span of isomorphism classes of posets, P, has a Newtonian coalgebra structure. We observe that the ab-index is a Newtonian coalgebra map from the vector space P to the algebra of polynomials in the noncommutative variables a and b. This enables us to obtain explicit formulas showing how the cd-index of the face lattice of a convex polytope changes when taking the pyramid and the prism of the polytope and the corresponding operations on posets. As a corollary, we have new recursion formulas for the cd-index of the Boolean algebra and the cubical lattice. Moreover, these operations also have interpretations for certain classes of permutations, including simsun and signed simsun permutations. We prove an identity for the shelling components of the simplex. Lastly, we show how to compute the ab-index of the Cartesian product of two posets given the ab-indexes of each poset.     

Unimodality and Lie Superalgebras

It is well-known how the representation theory of the Lie algebra sl(2, ?) can be used to prove that certain sequences of integers are unimodal and that certain posets have the Sperner property. Here an analogous theory is developed for the Lie superalgebra osp(1,2). We obtain new classes of unimodal sequences (described in terms of cycle index polynomials) and a new class of posets (the “super analogue” of the lattice L(m,n) of Young diagrams contained in an m × n rectangle) which have the Sperner property.     

Combinatorics & Topology of Stratifications of The Space of Monic Polynomials With Real Coefficients

We study the stratification of the space of monic polynomials with real coefficients according to the number and multiplicities of real zeros. In the first part, for each of these strata we provide a purely combinatorial chain complex calculating (co)homology of its one-point compactification and describe the homotopy type by order complexes of a class of posets of compositions. In the second part, we determine the homotopy type of the one-point compactification of the space of monic polynomials of fixed degree which have only real roots (i.e., hyperbolic polynomials) and at least one root is of multiplicity k. More generally, we describe the homotopy type of the one-point compactification of strata in the boundary of the set of hyperbolic polynomials, that are defined via certain restrictions on root multiplicities, by order complexes of posets of compositions. In general, the methods are combinatorial and the topological problems are mostly reduced to the study of partially ordered sets.     

Enumeration by kernel positions

We introduce a class of two-player games on posets with a rank function, in which each move of the winning strategy is unique. This allows one to enumerate the kernel positions by rank. The main example is a simple game on words in which the number of kernel positions of rank n is a signed factorial multiple of the nth Bernoulli number of the second kind. Generalizations to the degenerate Bernoulli numbers and to negative integer substitutions into the Bernoulli polynomials are developed. Using an appropriate scoring system for each function with an appropriate Newton expansion we construct a game in which the expected gain of a player equals the definite integral of the function on the interval [0,1].     

Pointed and multi-pointed partitions of type A and B

The aim of this paper is to define and study pointed and multi-pointed partition posets of type A and B (in the classification of Coxeter groups). We compute their characteristic polynomials, incidence Hopf algebras and homology groups. As a corollary, we show that some operads are Koszul over .     

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.     

Posets on up to 16 Points

In this article we describe a very efficient method to construct pairwise non-isomorphic posets (equivalently, T ₀ topologies). We also give the results obtained by a computer program based on this algorithm, in particular the numbers of non-isomorphic posets on 15 and 16 points and the numbers of labelled posets and topologies on 17 and 18 points.     

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.     

Z-Join Spectra of Z-Supercompactly Generated Lattices

The main result of this paper is a generalization of the classical equivalence between the category of continuous posets and the category of completely distributive lattices, based on the fact that the continuous posets are precisely the spectra of completely distributive lattices. Here we show that for so-called hereditary and union complete subset selections Z, the category of Z-continuous posets is equivalent (via a suitable spectrum functor) to the category of Z-supercompactly generated lattices; these are completely distributive lattices with a join-dense subset of certain Z-hypercompact elements. By appropriate change of the morphisms, these equivalences turn into dualities. We present two different approaches: the first one directly uses the Z-join ideal completion and the Z-below relation; the other combines two known equivalence theorems, namely a topological representation of Z-continuous posets and a general lattice theoretical representation of closure spaces.     

A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x)–h _L (y)|≤k, where h _L (x) is the height of x in L. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3. We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal of specific comparisons. The first and second authors were supported during this research by National Science Foundation VIGRE grant DMS-0135290.     

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.     

Z-Semicontinuous Posets

Z-semicontinuous posets include semicontinuous lattices and Z-continuous posets as special cases. We characterized when the associated Z-waybelow relation is multiplicative and also make a topological connection.     

A Characterisation of Posets that Are nearly Antichains

We present a characterisation of posets of size n with linear discrepancy n − 2. These are the posets that are “furthest” from a linear order without being an antichain. This revised version was published online in September 2006 with corrections to the Cover Date.     

q-Weighted log-concavity and q-product theorem on the normality of posets

We show that q-weighted log-concavity and the strict normalized matching property are preserved under the q-direct product over weighted posets. As consequences, two classes of weighted posets including the finite linear lattices are strictly q-weighted log-concave and strictly normal.     

Polygon Posets and the Weak Order of Coxeter Groups

We explore the connection between polygon posets, which is a class of ranked posets with an edge-labeling which satisfies certain polygon properties, and the weak order of Coxeter groups. We show that every polygon poset is isomorphic to a join ideal in the weak order, and for Coxeter groups where no pair of generators have infinite order the converse is also true.The class of polygon posets is seen to include the class of generalized quotients defined by Björner and Wachs, while itself being included in the class of alternative generalized quotients also considered by these authors. By studying polygon posets we are then able to answer an open question about common properties of these two classes.     

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.     

The Number of Unlabeled Orders on Fourteen Elements

Lacking an explicit formula for the numbers T ₀(n) of all order relations (equivalently: T ₀ topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too.