Posets and linear extensions

2026-08-17 Improve this page

#Posets

A poset is a set $P$ with a partial order $\leq_P:$ the relation is reflexive, antisymmetric, and transitive. We write $x\lt_P y$ if $x\leq_P y$ and $x\neq y.$ A cover relation is a relation $x\lessdot_P y$ such that $x\lt_P y$ and there is no $z$ with $x\lt_P z\lt_P y.$ The Hasse diagram of $P$ draws only these cover relations.

Two basic examples are the chain $1\lt 2\lt \dotsb \lt n$ and the antichain on $n$ elements, in which no two distinct elements are comparable. Posets are useful because many combinatorial objects are naturally sets with precedence constraints: boxes in a Young diagram, roots in a root poset, subsets ordered by inclusion, or independent sets ordered by inclusion.

#Linear extensions

Let $P$ be a finite poset with $n$ elements. A linear extension of $P$ is a total ordering $(p_1,p_2,\dotsc,p_n)$ of the elements of $P$ such that \[p_i\lt_P p_j \quad\Longrightarrow\quad i\lt j.\] Equivalently, it is an order-preserving bijection $P\to [n].$ We write $e(P)$ for the number of linear extensions of $P.$

Example (Three small posets).

Let $P$ be the poset with two minimal elements $a,b$ and one maximal element $c,$ so that $a\lt c$ and $b\lt c.$ Its linear extensions are \[(a,b,c),\qquad (b,a,c).\] For the chain $a\lt b\lt c,$ there is exactly one linear extension: $(a,b,c).$ For the antichain on $\{a,b,c\},$ every ordering is allowed, so there are $3!=6$ linear extensions.

Counting linear extensions is difficult in general: G. Brightwell and P. Winkler prove that this counting problem is #P-complete [BW91]. This is one reason why product formulas, recurrences, and special poset classes are valuable.

#Jordan–Hölder sets

A linear extension is usually a word in the elements of $P.$ A Jordan–Hölder set records instead the labels that appear along a linear extension.

More precisely, let $w:P\to [n]$ be a bijective labeling. The labeled poset is the pair $(P,w).$ A labeling is natural if $x\lt_P y$ implies $w(x)\lt w(y).$ The Jordan–Hölder set of the labeled poset $(P,w)$ is \[\mathcal{L}(P,w) \coloneqq \{\sigma\in\symS_n : \sigma^{-1}\circ w \text{ is order-preserving}\}.\] Thus $\sigma$ is the word of labels seen in some linear extension of $P.$ The poset determines the possible element orders; the labeling translates those orders into permutations.

Example (Same poset, different labels).

Let $P$ be the poset $a,b\lt c.$ With the natural labeling $w(a)=1,$ $w(b)=2,$ and $w(c)=3,$ the Jordan–Hölder set is \[\mathcal{L}(P,w)=\{123,213\}.\] If we relabel by $w(c)=1,$ $w(a)=2,$ and $w(b)=3,$ then the linear extensions of the underlying poset are still $(a,b,c)$ and $(b,a,c),$ but the Jordan–Hölder set becomes \[\mathcal{L}(P,w)=\{231,321\}.\] This distinction is important in the theory of $P$-partitions, where descent sets of the label words control the expansion in the fundamental quasisymmetric basis.

#$P$-Eulerian polynomials

Let $(P,w)$ be a labeled poset. The $P$-Eulerian polynomial is the descent generating polynomial of the Jordan–Hölder set: \[W_{P,w}(t) \coloneqq \sum_{\sigma\in\mathcal{L}(P,w)} t^{|\DES(\sigma)|}.\] If the labeling is understood, or if $P$ is naturally labeled, we often write $W_P(t).$

Example (Relabeled Jordan–Hölder sets).

For the naturally labeled poset $1,2\lt 3,$ the Jordan–Hölder set is $\{123,213\}.$ Thus \[W_P(t)=1+t,\] because $123$ has no descent and $213$ has one descent. With the relabeling from the previous example, the Jordan–Hölder set is $\{231,321\},$ so the corresponding labeled-poset Eulerian polynomial is $t+t^2.$

The $P$-Eulerian polynomial appears in the Ehrhart theory of order polytopes: the $h^*$-polynomial of $\mathcal{O}(P)$ is the $P$-Eulerian polynomial for a natural labeling. This is the bridge between linear extensions, descent statistics, and real-rootedness questions for posets. A famous question in this direction was the Neggers–Stanley conjecture, which asked for real-rootedness of these polynomials in broad generality.

Example (Small naturally labeled posets).

The polynomial $W_P(t)$ records the descent distribution of the linear extensions; it is not the same data as the poset itself.

Poset P Linear extensions W_P(t) Chain 1 < 2 < 3 123 1 1, 2 < 3 123, 213 1 + t 1 < 3, with 2 isolated 123, 132, 213 1 + 2t Antichain on {1, 2, 3} S₃ 1 + 4t + t²

#Order ideals, filters and antichains

An order ideal of a poset $P$ is a subset $I\subseteq P$ such that $x\in I$ and $y\leq_P x$ imply $y\in I.$ Dually, an order filter is an upward-closed subset. An antichain is a subset whose elements are pairwise incomparable.

Order ideals and antichains are equivalent data: an ideal is determined by its maximal elements, and those maximal elements form an antichain. This is the starting point for many actions such as rowmotion and promotion, and it is also why the lattice of ideals of a poset appears throughout algebraic combinatorics.

Example (Ideals in a three-element poset).

For the poset $a,b\lt c,$ the order ideals are \[\emptyset,\qquad \{a\},\qquad \{b\},\qquad \{a,b\},\qquad \{a,b,c\}.\] The maximal elements of these ideals are respectively \[\emptyset,\qquad \{a\},\qquad \{b\},\qquad \{a,b\},\qquad \{c\},\] which are precisely the antichains of the poset.

Independent sets of a graph or matroid can also be ordered by inclusion. For a graph $G,$ the independent sets form a down-set in the Boolean lattice $2^{V(G)}.$ This poset is usually not a lattice under union, but it is a natural way to turn graph-theoretic independence into an ordered object.

#Hook formulas

Many important posets have unexpectedly simple formulas for $e(P).$

For a partition $\lambda,$ the boxes of its Young diagram form a poset by declaring a box to be less than the boxes weakly southeast of it. A standard Young tableau of shape $\lambda$ is the same thing as a linear extension of this Young-diagram poset. The classical hook formula says \[e(\lambda)=|\SYT(\lambda)| = \frac{|\lambda|!}{\prod_{\square\in\lambda} h(\square)}.\] Equivalently, this is the Frame–Robinson–Thrall hook-length formula [FBRT54]. See also the $q$-hook formula.

There is an analogous hook formula for rooted tree posets. If $T$ is a rooted tree viewed as a poset with $u\leq_T v$ when $u$ is on the path from the root to $v,$ then \[e(T)=\frac{|T|!}{\prod_{v\in T} |T_v|},\] where $T_v$ is the rooted subtree consisting of $v$ and all its descendants. This formula is discussed, for example, by D. E. Knuth [Knu98].

Hook formulas also exist for shifted shapes, $d$-complete posets, and several other structured families. The important contrast is that such formulas are special: for an arbitrary poset, counting linear extensions is computationally hard [BW91].

#Order and chain polytopes

Finite posets have a direct polyhedral avatar. The order polytope $\mathcal{O}(P)$ is the set of functions $f:P\to [0,1]$ such that $x\leq_P y$ implies $f(x)\leq f(y).$ The chain polytope $\mathcal{C}(P)$ is cut out by nonnegativity and the inequalities \[f(x_1)+f(x_2)+\dotsb+f(x_k)\leq 1\] for every chain $x_1\lt{}_P x_2\lt{}_P\dotsb\lt{}_P x_k.$ Stanley introduced these two poset polytopes in [Sta86].

The normalized volume of $\mathcal{O}(P)$ is $e(P),$ and the $h^*$-polynomial of $\mathcal{O}(P)$ is the descent generating polynomial of the linear extensions of $P.$ Thus order polytopes connect linear extensions to Ehrhart theory and to real-rootedness questions for descent polynomials.

The same story appears in the theory of $P$-partitions: the order polynomial $\Omega_P(m)$ counts order-preserving maps $P\to [m],$ and its generating function has numerator the $P$-Eulerian polynomial.

#Promotion and rowmotion

Posets also carry natural dynamics. Promotion can be defined on linear extensions of a poset; see R. Stanley [Sta09]. For arbitrary labelings, C. Defant and N. Kravitz introduce promotion sorting [DK22]. Promotion is also one of the standard cyclic actions behind CSPs for rectangular standard Young tableaux and Kreweras words.

Example (Promotion on a small poset).

Let $P$ be the poset $a,b\lt c.$ The two linear extensions are \[(a,b,c),\qquad (b,a,c).\] Under promotion, the first extension follows the chain $a\lt c$ and becomes $(b,a,c).$ Similarly, $(b,a,c)$ follows the chain $b\lt c$ and becomes $(a,b,c).$ Thus promotion has one orbit of size $2$ on this example.

On order ideals, one important action is rowmotion: send an ideal to the ideal generated by the minimal elements outside it. Root posets and minuscule posets give many cyclic-sieving examples; see the root poset and minuscule poset sections on cyclic sieving. Rowmotion and its toggle variants are also central examples in homomesy.

Example (Rowmotion on a chain).

Let $P$ be the chain $x\lt y\lt z.$ Its order ideals form one rowmotion orbit: \[\emptyset \longmapsto \{x\} \longmapsto \{x,y\} \longmapsto \{x,y,z\} \longmapsto \emptyset.\] Indeed, from $\{x\}$ the minimal element outside the ideal is $y,$ and the ideal generated by $y$ is $\{x,y\}.$

#Some classes of posets

The width of a poset is the largest size of an antichain. Width-one posets are chains; width-two posets already contain rich examples such as the posets attached to skew Ferrers diagrams and lattice path matroids.

A ranked poset is a poset with a rank function $\rho:P\to\setN$ such that $x\lessdot_P y$ implies $\rho(y)=\rho(x)+1.$ A poset is graded if every maximal chain in every interval has the same length; finite graded posets are ranked after choosing the rank of each minimal element.

A lattice is a poset in which every two elements have a meet and a join, usually written $x\wedge y$ and $x\vee y.$ A basic source of lattices is the set $J(P)$ of order ideals of a finite poset $P,$ ordered by inclusion.

The Boolean lattice $B_n$ is the lattice of all subsets of $[n],$ ordered by inclusion. A distributive lattice is a lattice in which meet and join distribute over one another. The lattices $J(P)$ of order ideals are distributive, and Birkhoff’s representation theorem says that every finite distributive lattice arises this way; see [Sta11].

A series-parallel poset is built from one-element posets using two operations: disjoint union, also called parallel composition, and ordinal sum, also called series composition. Such posets are often amenable to recursive enumeration because both operations have simple effects on linear extensions. These operations preserve real-rootedness of $P$-Eulerian polynomials; see the real-rootedness discussion.

A poset is $(3+1)$-free if it has no induced subposet consisting of a three-element chain together with an element incomparable to all three elements of the chain. These posets are central in the study of incomparability graphs and chromatic symmetric functions: V. Gasharov proved Schur positivity for incomparability graphs of $(3+1)$-free posets [Gas96]. They also occur in chromatic quasisymmetric functions.

Example ($(3+1)$-free and not $(3+1)$-free).

Every poset of height at most two is automatically $(3+1)$-free, since it has no three-element chain. For example, the diamond-shaped poset with relations $a,b\lt c,d$ is $(3+1)$-free.

In contrast, take a chain $a\lt b\lt c$ and add an element $d$ that is incomparable to $a,b,c.$ The induced subposet on $\{a,b,c,d\}$ is exactly a $(3+1),$ so this poset is not $(3+1)$-free.

A poset is $(2+2)$-free if it has no induced subposet consisting of two disjoint two-element chains. Equivalently, it is an interval order: its elements can be represented by intervals on the real line, ordered by lying completely to the left.

A unit interval order is an interval order that can be represented using intervals of equal length. Equivalently, it is both $(3+1)$-free and $(2+2)$-free. Its incomparability graph is a unit interval graph. This is the setting of many Schur-positivity results for chromatic quasisymmetric functions, and the reduced setting for the Stanley–Stembridge $\elementaryE$-positivity problem.

Bibliography

[BW91]Graham Brightwell and Peter Winkler. Counting linear extensions. Order, 8(3):225–242, 1991.

.bib

@Article{BrightwellWinkler1991,
author={Graham Brightwell and Peter Winkler},
title={Counting linear extensions},
journal={Order},
year={1991},
volume={8},
number={3},
pages={225--242},
issn={1572-9273},
doi={10.1007/BF00383444}
}

[DK22]Colin Defant and Noah Kravitz. Promotion sorting. Order, 40(1):199–216, 2022.

.bib

@article{DefantKravitz2022,
  author = {Defant, Colin and Kravitz, Noah},
  title = {Promotion sorting},
  year = {2022},
  journal = {Order},
  volume = {40},
  number = {1},
  pages = {199--216},
  publisher = {Springer Science and Business Media LLC},
  doi = {10.1007/s11083-022-09603-9},
  url = {http://dx.doi.org/10.1007/s11083-022-09603-9},
  issn = {1572-9273}
}

[FBRT54]J. S. Frame, G. B. Robinson and R. M. Thrall. The hook graphs of the symmetric group. Canad. J. Math., 6:316–325, 1954.

.bib

@article{FrameRobinsonThrall,
author = {J. S. Frame and G. de B. Robinson and R. M. Thrall},
title = {The hook graphs of the symmetric group},
journal = {Canad. J. Math.},
volume = {6},
year = {1954},
pages = {316--325}
}

[Gas96]Vesselin Gasharov. Incomparability graphs of $(3+1)$-free posets are $s$-positive. Discrete Mathematics, 157(1):193–197, 1996.

.bib

@article{Gasharov1996,
title = {Incomparability graphs of $(3+1)$-free posets are $s$-positive},
journal = {Discrete Mathematics},
volume = {157},
number = {1},
pages = {193--197},
year = {1996},
issn = {0012-365X},
doi = {10.1016/S0012-365X(96)83014-7},
url2 = {http://www.sciencedirect.com/science/article/pii/S0012365X96830147},
author = {Vesselin Gasharov}
}

[Knu98]Donald E. Knuth. The art of computer programming, volume 3: Sorting and searching. Addison Wesley Longman Publishing Co., Inc., Second, 1998.

.bib

@book{Knuth1998ArtOfProgramming,
 author = {Donald E. Knuth},
 title = {The Art of Computer Programming,  Volume 3: Sorting and Searching},
 year = {1998},
 edition = {Second},
 isbn = {0-201-89685-0},
 publisher = {Addison Wesley Longman Publishing Co., Inc.},
 address = {Redwood City, CA, USA},
}

[Sta09]Richard P. Stanley. Promotion and evacuation. The Electronic Journal of Combinatorics, 16(2), April 2009.

.bib

@article{Stanley2009,
  doi = {10.37236/75},
  url2 = {https://doi.org/10.37236/75},
  year = {2009},
  month = apr,
  publisher = {The Electronic Journal of Combinatorics},
  volume = {16},
  number = {2},
  author = {Richard P. Stanley},
  title = {Promotion and Evacuation},
  journal = {The Electronic Journal of Combinatorics}
}

[Sta86]Richard P. Stanley. Two poset polytopes. Discrete & Computational Geometry, 1(1):9–23, 1986.

.bib

@Article{Stanley86TwoPosetPolytopes,
author = {Richard P. Stanley},
title={Two poset polytopes},
journal={Discrete \& Computational Geometry},
year={1986},
volume={1},
number={1},
pages={9--23},
issn={1432-0444},
doi={10.1007/BF02187680}
}

[Sta11]Richard P. Stanley. Enumerative Combinatorics: Volume 1. Cambridge University Press, Second, 2011.

.bib

@book{StanleyEC1,
 author = {Richard P. Stanley},
 title = {Enumerative {C}ombinatorics: {V}olume 1},
 year = {2011},
 isbn = {9781107602625},
 edition = {Second},
 doi = {10.1017/CBO9781139058520},
 publisher = {Cambridge University Press}
}

The symmetric functions catalog

#Posets

#Linear extensions

#Jordan–Hölder sets

#\(P\)-Eulerian polynomials

#Order ideals, filters and antichains

#Hook formulas

#Order and chain polytopes

#Promotion and rowmotion

#Some classes of posets

Bibliography