Some results on counting linearizations of posets
Open Access Publications from the University of California

## Some results on counting linearizations of posets

• Author(s): Bergman, George M
• et al.
Abstract

In section 1 we consider a 3-tuple $S=(|S|,\preccurlyeq,E)$ where $|S|$ is a finite set, $\preccurlyeq$ a partial ordering on $|S|,$ and $E$ a set of unordered pairs of distinct members of $|S|,$ and study, as a function of $n\geq 0,$ the number of maps $\varphi:|S|\to\{1,\dots,n\}$ which are both isotone with respect to the ordering $\preccurlyeq,$ and have the property that $\varphi(x)\neq \varphi(y)$ whenever $\{x,y\}\in E.$ We prove a number-theoretic result about this function, and use it in section 7 to recover a ring-theoretic identity of G. P. Hochschild. In section 2 we generalize a result of R. Stanley on the sign-imbalance of posets in which the lengths of all maximal chains have the same parity. In sections 3-6 we study the linearization-count and sign-imbalance of a lexicographic sum of $n$ finite posets $P_i$ $(1\leq i\leq n)$ over an $n$-element poset $P_0.$ We note how to compute these values from the corresponding counts for the given posets $P_i,$ and for a lexicographic sum over $P_0$ of chains of lengths $\mathrm{card}(P_i).$ This makes the behavior of lexicographic sums of chains over a finite poset $P_0$ of interest, and we obtain some general results on the linearization-count and sign-imbalance of these objects.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.