Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#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}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 6.2 Antichain and Chain Partitioning
Duals, Cover Graphs, and Comparability Graphs.
Dual of
\(\bfP\) is denoted
\(\bfP^d\)
Bob’s Claims:
Only linear orders have paths as cover graphs.
A poset and its dual have the same cover graph and the same comparability graph.
Any two posets with the same cover graph have the same height and the same width.
Any two posets with the same comparability graph have the same height and the same width.
Height and Antichain Partitioning.
Theorem 6.10 . Dual of Dilworth’s Theorem.
A poset \(\bfP=(X,P')\) has height \(h\) if and only if \(h\) is the smallest number so that there exist \(h\) disjoint antichains \(A_{1},\dots, A_{h}\) with
\begin{equation*}
X= A_{1}\cup A_{2}\cup\cdots\cup A_{h}\text{.}
\end{equation*}
Proof by algorithm.
Let
\(\bfP_{1} = \bfP\text{.}\) Place minimal elements of
\(\bfP_{1}\) in
\(A_{1}\text{.}\) Let
\(\bfP_{2}\) be formed from
\(\bfP_{1}\) by deleting the points in
\(A_{1}\text{.}\) Place minimal elements of
\(\bfP_{2}\) in
\(A_{2}\text{.}\)
General step: Form
\(\bfP_{i+1}\) by removing
\(A_{i}\) from
\(\bfP_{i}\text{.}\) Let
\(A_{i+1}\) be the minimal elements of
\(\bfP_{i+1}\text{.}\)
Continue until every point is in an antichain.
The order diagram of a poset with 7 points. The points are labeled with letters from
\(a\) to
\(f\text{.}\)
Chain Partitioning and Width. Let’s look back at the Dual of Dilworth’s Theorem. What would be a similar result for width?
Theorem 6.11 . Dilworth’s Theorem.
Let \(\bfP=(X,P')\) be a poset. Then \(w\) is the width of \(\bfP\) if and only if \(w\) is the smallest number so that there exist \(w\) disjoint chains \(C_{1},C_{2},\dots C_{w}\) with
\begin{equation*}
X=C_{1}\cup C_{2}\cup \cdots\cup C_{w}.
\end{equation*}
