Order series of labelled posets
Given a finite labelled poset \((P,<,\omega)\), let \(O(P)\) denote the set of all finite sequences \(\sigma= (S_ 1,\dots, S_ m)\) such that: each \(S_ i\) is a non-empty subset of \(P\), each \(S^ 2_ i\) contains no inversions \((a\langle b,\omega(a)\rangle (b))\) of \(P\), and for each \(i=1,\dots, m\), \(S_ i\cap \downarrow (S_ 1\bigcup \dots\bigcup S_{i-1}) \subseteq \max(S_ 1\cup \dots\cup S_{i-1})\) \([\downarrow S= \{a\leq b\) for \(b\in S\}]\), \(\max S= \{a\in S\mid b>a\) implies \(b\not\in S\}]\). Then \(\# \sigma=m\), \(X= \{X_ a\mid a\in P\}\), \(X^ f=\prod_{a\in P} X_ a^{fa}\), \(\text{el}(\sigma, a)= \text{el}(\sigma)(a)= \# \{i\mid a\in S_ i\}\), where the order-series \(\Omega_ p (t,x)= \Sigma(\#\sigma) X^{\text{el}(\sigma)}\),and the \(E\)-series \(E_ p (t,X)= \Sigma t^{\#\sigma} X^{\text{el}(\sigma)}\), with the summation extending over all \(\sigma\) in \(O(P)\), are multi-analogs of the order polynomials and the \(E\)-polynomials respectively, and like them connected by a formula \(\sum_{m\geq 0} \Omega_ p (m,X) t^ m= (1-t)^{-1}\cdot E_ p (t(1-t)^{-1}, X)\). Using a variety of methods from enumerative combinatorics as well as a collection of nifty insights, the author is able to determine some rather large classes of \(E\)-series including strictly (i.e., order-reversing) labelled chains, antichains, naturally labelled chains, and interval posets where the Moebius function plays a role. Furthermore, in Theorem 2.1, the \(E\)-series \(E_ p(t,X)\) is interpreted naturally as the enumeration series of all walks on a particular finite directed multigraph associated with \((P,<,\omega)\). An interesting conjecture concerning the zeros of \(E_ p(t,X)\) is also posed, further establishing the reach of what was originally an observation based on a set of examples handled by (now very primitive) computer methods and resisted for some years by editors and referees as possibly meaningful. It appears that the author of this forward marching paper is bound to make many dents at least in a problem whose mysteries have not all been extracted yet.
scientific article; zbMATH DE number 540218