Order series of labelled posets
type: Item
instance of: scholarly article
title: Order series of labelled posets
zbMATH Open document ID: 0801.06002
DOI: 10.1007/BF01111301
author: David G. Wagner
published in: Order
publication date: 1994-12-01T00:00:00Z
review text: 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…
reviewed by: J. Neggers
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A19
zbMATH DE Number: 540218
zbMATH Keywords: Moebius inversion
zbMATH Keywords: transfer matrix method
zbMATH Keywords: labelled poset
zbMATH Keywords: \(E\)-series
zbMATH Keywords: order polynomials
zbMATH Keywords: \(E\)-polynomials
zbMATH Keywords: enumerative combinatorics
zbMATH Keywords: interval posets
zbMATH Keywords: Moebius function
zbMATH Keywords: enumeration series
zbMATH Keywords: multigraph
MaRDI profile type: Publication
cites work: Unimodal, log-concave and Pólya frequency sequences in combinatorics
cites work: Log-concavity and combinatorial properties of Fibonacci lattices
cites work: Counting linear extensions
cites work: Transitiv orientierbare Graphen
cites work: Intransitive Indifference in Preference Theory: A Survey
cites work: Q4196466
cites work: A multiindexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences
cites work: Ordered structures and partitions
cites work: Hilbert functions of graded algebras
cites work: Q3748279
cites work: Enumeration of functions from posets to chains
cites work: Multipartition Series
description: scientific article; zbMATH DE number 540218