A New Approach to Order Polynomials of Labeled Posets and Their Generalizations

In the early 1970's, Richard Stanley and Kenneth Johnson introduced and laid the groundwork for studying the order polynomial of partially ordered sets (posets). Decades later, Hamaker, Patrias, Pechenik, and Williams introduced the term "doppelgangers": equivalence classes of posets under the equivalence relation given by equality of the order polynomial. We provide necessary and sufficient conditions on doppelgangers through application of both old and novel tools, includin...

M\"obius inversion of functions on partially ordered sets (posets) $\mathcal{P}$ is a classical tool in combinatorics. For finite posets it consists of two, mutually inverse, linear transformations called zeta and M\"obius transform, respectively. In this paper we provide novel fast algorithms for both that require $O(nk)$ time and space, where $n = |\mathcal{P}|$ and $k$ is the width (length of longest antichain) of $\mathcal{P}$, compared to $O(n^2)$ for a direct computatio...

The P-Eulerian polynomial counts the linear extensions of a labeled partially ordered set, P, by their number of descents. It is known that the P-Eulerian polynomials are real-rooted for various classes of posets P. The purpose of this paper is to extend these results to polynomials in several variables. To this end we study multivariate extensions of P-Eulerian polynomials and prove that for certain posets these polynomials are stable, i.e., non-vanishing whenever all variab...

The present paper deals with Bernstein polynomials and Frobenius-Euler numbers and polynomials. We apply the method of generating function and fermionic p-adic integral representation on Zp, which are exploited to derive further classes of Bernstein polynomials and Frobenius-Euler numbers and polynomials. To be more precise we summarize our results as follows, we obtain some combinatorial relations between Frobenius-Euler numbers and polynomials. Furthermore, we derive an int...

In this paper we outline a Matrix Ansatz approach to some problems of combinatorial enumeration. The idea is that many interesting quantities can be expressed in terms of products of matrices, where the matrices obey certain relations. We illustrate this approach with applications to moments of orthogonal polynomials, permutations, signed permutations, and tableaux.

The $P$-partition generating function of a (naturally labeled) poset $P$ is a quasisymmetric function enumerating order-preserving maps from $P$ to $\mathbb{Z}^+$. Using the Hopf algebra of posets, we give necessary conditions for two posets to have the same generating function. In particular, we show that they must have the same number of antichains of each size, as well as the same shape (as defined by Greene). We also discuss which shapes guarantee uniqueness of the $P$-pa...

We study generating functions of strict and non-strict order polynomials of series-parallel posets, called order series. These order series are closely related to Ehrhart series and h*-polynomials of the associated order polytopes. We explain how they can be understood as algebras over a certain operad of posets. Our main results are based on the fact that the order series of chains form a basis in the space of order series. This allows to reduce the search space of an algori...

A poset is (3+1)-free if it does not contain the disjoint union of chains of length 3 and 1 as an induced subposet. These posets are the subject of the (3+1)-free conjecture of Stanley and Stembridge. Recently, Lewis and Zhang have enumerated \emph{graded} (3+1)-free posets, but until now the general enumeration problem has remained open. We enumerate all (3+1)-free posets by giving a decomposition into bipartite graphs, and obtain generating functions for (3+1)-free posets w...

A number of recent papers treated the representation theory of partially ordered sets in unitary spaces with the so called orthoscalar relation. Such theory generalizes the classical theory which studies the representations of partially ordered sets in linear spaces. It happens that the results in the unitary case are well-correlated with those in the linear case. The purpose of this article is to shed light on this phenomena.

We survey all known examples of finite posets whose order polynomials have product formulas, and we propose the heuristic that these are the same posets with good dynamical behavior. Here the dynamics in question are the actions of promotion on the linear extensions of the poset and rowmotion on the P-partitions of the poset.