zbMATH — the first resource for mathematics

A recurrence for linear extensions. (English) Zbl 0692.06001
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)\).
Reviewer: L.Skula

06A06 Partial orders, general
06A05 Total orders
Full Text: DOI
[1] B. Dreesen, W. Poguntke, and P. Winkler (1985) Comparability invariance of the fixed point property, Order 2, 269-274. · Zbl 0577.06005
[2] M. Habib (1984) Comparability invariants, Ann. Discrete Math. 23, 371-386.
[3] D. Kelly (1986) Invariants of finite comparability graphs, Order 3, 155-158. · Zbl 0616.05059 · doi:10.1007/BF00390105
[4] M. P. Sch├╝tzenberger (1972) Promotion des morphismes d’ensembles ordonnes, Discrete Math. 2, 73-94. · Zbl 0279.06001 · doi:10.1016/0012-365X(72)90062-3
[5] R. Stanley (1986) Two poset polytopes, Discrete Comput. Geom. 1, 9-23. · Zbl 0595.52008 · doi:10.1007/BF02187680
[6] R. Stanley (1986) Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA. · Zbl 0608.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.