Some results on counting linearizations of posets
Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Some results on counting linearizations of posets

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

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.

Main Content
Current View