6.4: Linear Extensions of Partially Ordered Sets

Last updated
Save as PDF

Page ID: 97890

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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

Screen Shot 2022-03-04 at 9.49.07 AM.png — Figure **6.23.** A poset and its linear extensions

Discussion 6.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<y\) in \(L\)? All the well known sorting algorithms (bubble sort, merge sort, quick sort, etc.) proceed in this manner.

Discussion 6.25

Given the poset \(P=(X,P)\) shown in Figure 6.5 and the problem of determining an unknown linear extension of \(P\), how should Alice decide which question (of the form: Is \(x<y\) in \(L\)?) 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?