Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section6.4Linear Extensions of Partially Ordered Sets

Let \(\PXP\) be a partially ordered set. A linear order \(L\) on \(X\) is called a linear extension (also, a topological sort) of \(P\text{,}\) if \(x\lt y\) in \(L\) whenever \(x\lt y\) in \(P\text{.}\) For example, the table displayed in Figure 6.23 shows that our familiar example \(\bfP_3\) has 11 linear extensions.

<<SVG image is unavailable, or your browser cannot render it>>

\begin{equation*} \begin{array}{ccccccccccc} L_1\amp L_2 \amp L_3 \amp L_4 \amp L_5 \amp L_6 \amp L_7 \amp L_8 \amp L_9 \amp L_{10} \amp L_{11}\\[.2in] d \amp d \amp d \amp b \amp d \amp d \amp d \amp b \amp d \amp d \amp b \\ c \amp c \amp b \amp d \amp c \amp c \amp b \amp d \amp c \amp b \amp d \\ w \amp b \amp c \amp c \amp w \amp b \amp c \amp c \amp b \amp c \amp c \\ b \amp w \amp w \amp w \amp b \amp w \amp w \amp w \amp z \amp z \amp z \\ a \amp a \amp a \amp a \amp z \amp z \amp z \amp z \amp w \amp w \amp w \\ z \amp z \amp z \amp z \amp a \amp a \amp a \amp a \amp a \amp a \amp a \\ \end{array} \end{equation*}

Figure6.23A poset and its linear extensions
Discussion6.24

Bob says that he is not convinced that every finite poset has a linear extension. Alice says that it is easy to show that they do. Is she right?

Carlos says that there are subtleties to this question when the ground set \(X\) is infinite. You might want to do a web search on the name Szpilrajn and read about his contribution to this issue.

The classical sorting problem studied in all elementary computer science courses is to determine an unknown linear order \(L\) of a set \(X\) by asking a series of questions of the form: Is \(x\lt y\) in \(L\text{?}\) All the well known sorting algorithms (bubble sort, merge sort, quick sort, etc.) proceed in this manner.

Here is an important special case: determine an unknown linear extension \(L\) of a poset \(\bfP\) by asking a series of questions of the form: Is \(x \lt y\) in \(L\text{?}\)

Discussion6.25

Given the poset \(\PXP\) shown in Figure 6.5 and the problem of determining an unknown linear extension of \(P\text{,}\) how should Alice decide which question (of the form: Is \(x\lt y\) in \(L\text{?}\)) to ask?

How would you like to be assigned to count the number of linear extensions of this poset? In general, how hard is it to determine the number of linear extensions of a poset? Could you (and your computer) do this count for a poset on \(100,000\) points?