A recurrence for linear extensions
type: Item
instance of: scholarly article
title: A recurrence for linear extensions
zbMATH Open document ID: 0692.06001
DOI: 10.1007/BF00341632
author: Takayuki Hibi
author: Richard P. Stanley
author: Paul Edelman
published in: Order
publication date: 1989-01-01T00:00:00Z
review text: 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)\).
reviewed by: Ladislav Skula
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06A05
zbMATH DE Number: 4132217
zbMATH Keywords: number of linear extensions of a finite partially ordered set
zbMATH Keywords: saturated chains
zbMATH Keywords: comparability graphs
MaRDI profile type: Publication
cites work: Comparability invariance of the fixed point property
cites work: Invariants of finite comparability graphs
cites work: Promotion des morphismes d'ensembles ordonnes
cites work: Two poset polytopes
cites work: Q3748279
description: scientific article; zbMATH DE number 4132217