A recurrence for linear extensions (Q583247): Difference between revisions

This article deals with the number e(P) of linear extensions of a finite partially ordered set P (the set P does not change). For the formulation of the main theorem the following notion is necessary. Let \(C=\{x_ 0<x_ 1<...<x_ m\}\) be a saturated chain in P \((x_{i+1}\) covers \(x_ i\) for \(0\leq i<m)\). Put \(P_ C=P-\{x_ 0\}\) if \(m=0\) and \(P_ C=(P-C)\cup \{x_{0,1},x_{1,2},...,x_{m-1,m}\},\) where \(x_{0,1},...,x_{m-1,m}\) are new elements. The partial ordering on \(P_ C\) is added by \(x_{0,1}<...<x_{m-1,m}\), \(y<x_{i,i+1}\) if \(y\in P-C\) and \(y<x_{i+1}\) in P, \(y>x_{i,i+1}\) if \(y\in P-C\) and \(y>x_ i\) in P. The authors prove the following three assertions: Theorem. Let \({\mathfrak C}\) be a set of saturated chains of P such that every maximal chain of P contains exactly one element of \({\mathfrak C}\). Then \(e(P)=\sum_{C}e(P_ C)\) (C\(\in {\mathfrak C}).\) Corollary. Let A be an antichain of P which intersects every maximal chain. Then \(e(P)=\sum_{x}e(P-\{x\})\) (x\(\in A).\) Proposition. If P and Q are finite posets with isomorphic comparability graphs, then \(e(P)=e(Q)\).