Chapter 17: Partially Ordered Sets and Lattice Theory

Can a poset be covered by as few chains as its widest antichain?

In project management and workflow design, some tasks must precede others, while other tasks can be executed in parallel. A partially ordered set (or poset) provides the natural mathematical language for recording these dependency constraints without inventing artificial comparisons that the problem domain does not supply.

Two fundamental questions arise when scheduling tasks under partial order constraints:

1. Sequential Scheduling (Chains): What is the minimum number of sequential pipelines (chains) required to execute all tasks?
2. Parallel Bottlenecks (Antichains): What is the maximum number of mutually independent tasks (antichains) that can be executed simultaneously?

Remarkably, the answers to these two dual optimization problems are identical. This chapter explores partially ordered sets, lattices, and order-based enumeration.

We build on partitions and structure types, inclusion–exclusion and Möbius inversion, and fundamentals of graph theory. The core starts with finite sets and relations. Abstract algebra becomes useful for incidence algebras, where we specify the operations explicitly; the optional topology section identifies its additional prerequisites.

17.1 Partial orders, Hasse diagrams, chains, and antichains

What & Definitions. A partial order on a set $P$ is a binary relation $\le$ satisfying three structural axioms for all $x, y, z \in P$:

1. Reflexivity: $x\le x$.
2. Antisymmetry: If $x\le y$ and $y\le x$, then $x=y$.
3. Transitivity: If $x\le y$ and $y\le z$, then $x\le z$.

A partially ordered set (or poset) is the pair $(P, \le)$. Write $x < y$ when $x\le y$ and $x\ne y$. Two distinct elements $x, y \in P$ are incomparable (written $x \parallel y$) if neither $x\le y$ nor $y\le x$ holds.

Chains vs. Antichains.

• A subset $C \subseteq P$ is a chain if any two elements in $C$ are comparable (total ordering on $C$). The height $h(P)$ of a poset is the maximum number of elements in a chain.
• A subset $A \subseteq P$ is an antichain if any two distinct elements in $A$ are incomparable. The width $w(P)$ of a poset is the maximum number of elements in an antichain.

Hasse Diagrams (Simplifying Order Visualizations). Direct graph drawings of partial orders become cluttered due to reflexive loops and transitive shortcut edges. Element $y$ covers $x$ (written $x\lessdot y$) if $x < y$ and there is no intermediate element $z$ such that $x < z < y$. A Hasse diagram represents the poset by drawing only cover relations as upward line segments from $x$ to $y$. All reflexive loops and transitive shortcut edges are omitted without losing information.

Running Example. Let $V=\{a,b,c\}$ with strict relations $a < c$ and $b < c$, while $a,b$ are incomparable. Both relations are covers. Its maximal chains are $\{a,c\}$ and $\{b,c\}$ (size 2), and its largest antichain is $\{a,b\}$ (size 2). Thus height and width are both 2. In a dependency interpretation, tasks $a,b$ must finish before task $c$ can begin.

Exercise. On $\{1,2,3,6\}$, order numbers by divisibility. List the covers, height, and width. Hint: Distinguish a cover from the transitive comparison $1 < 6$. Answer: The covers are $1\lessdot2$, $1\lessdot3$, $2\lessdot6$, $3\lessdot6$. Height is 3 (e.g., $1 < 2 < 6$) and width is 2, witnessed by antichain $\{2,3\}$.

17.2 Minimal/maximal elements, ideals, and filters

What & Definitions.

• An element $x \in P$ is minimal if no $y \in P$ satisfies $y < x$. An element $x \in P$ is maximal if no $y \in P$ satisfies $x < y$.
• A least element ($\hat{0}$) satisfies $\hat{0} \le x$ for all $x \in P$. A greatest element ($\hat{1}$) satisfies $x \le \hat{1}$ for all $x \in P$. Least and greatest elements, if they exist, are unique.
• An order ideal (or down-set) is a subset $I \subseteq P$ such that if $x \in I$ and $y \le x$, then $y \in I$. In scheduling, an ideal represents a set of completed tasks whose prerequisites are all satisfied.
• An order filter (or up-set) is a subset $F \subseteq P$ such that if $x \in F$ and $x \le y$, then $y \in F$. The complement $P \setminus I$ of any ideal is an order filter.
• The principal ideal generated by $x$ is $\downarrow x = \{y \in P : y \le x\}$. The principal filter is $\uparrow x = \{y \in P : x \le y\}$.

Structural Theorem (Ideals–Antichains Bijection). In any finite poset $P$, an ideal $I$ is uniquely determined by the antichain of its maximal elements $\max(I)$:

$$ I=\bigcup_{x\in\max(I)}\downarrow x. $$

Conversely, the downward closure of any antichain $A$ forms a unique ideal whose maximal elements are $A$. Thus, the number of order ideals in $P$ equals the number of antichains in $P$.

Exercise. Are $\{a,c\}$ and $\{c\}$ ideals of $V$? Are they filters? Hint: $b < c$. Answer: Neither is an ideal because both contain $c$ but omit required prerequisite $b$. Both are filters because every element above $a$ or $c$ is included.

17.3 Linear extensions and topological orderings

What & Definitions. A linear extension (or topological sort) of an $n$-element poset $P$ is a total order (permutation) $x_1, x_2, \ldots, x_n$ of $P$ that preserves the partial order: $x <_P y \implies x$ appears before $y$ in the linear sequence. Let $e(P)$ denote the total number of linear extensions of $P$, with $e(\varnothing)=1$.

Directing all Hasse edges upwards creates a Directed Acyclic Graph (DAG). Its topological orderings are precisely the linear extensions of $P$. In computing, topological sorting resolves build dependency chains (such as Makefile target execution or package installation orders).

First-Element Recurrence. The first element of any linear extension must be a minimal element of $P$. Removing it leaves a subposet $P \setminus \{x\}$. Summing over all minimal elements gives:

$$ e(P)=\sum_{x\in\min(P)}e(P\setminus\{x\}). $$

Ideal-Chain Bijection. Every prefix of a linear extension forms an order ideal. A sequence of ideals forming a saturated chain in $J(P)$:

$$ \varnothing = I_0 \subset I_1 \subset I_2 \subset \cdots \subset I_n = P \quad (|I_k|=k) $$

specifies a unique linear extension by reading the single element added at each step $I_k \setminus I_{k-1}$. Thus, the number of linear extensions $e(P)$ equals the number of maximal chains in the ideal lattice $J(P)$.

Exercise. Add an isolated element $d$ to $V$. How many linear extensions result? Hint: Insert $d$ into any of the 4 available slots in each linear extension of $V$. Answer: $4 \times e(V) = 4 \times 2 = 8$.

17.4 Dilworth's theorem and Mirsky's theorem

A chain partition covers $P$ using pairwise disjoint chains. An antichain partition covers $P$ using pairwise disjoint antichains. Dilworth's and Mirsky's theorems establish dualities between packing bounds and covering numbers.

Proof of Dilworth via Bipartite Matching. Let $|P| = n$. Construct a bipartite graph $B = (P_L, P_R, E)$ with left set $P_L = \{x_L : x \in P\}$ and right set $P_R = \{y_R : y \in P\}$. Add edge $x_L y_R \in E$ if $x <_P y$ in $P$.

A matching of size $k$ in $B$ chooses $k$ predecessor-successor links $x \to y$ in $P$. Since each vertex in $B$ is matched at most once, these links form $n - k$ path components (chains). Thus, a maximum matching of size $k$ produces a minimum chain partition of size $n - k$. By König's Theorem, maximum matching size $k$ equals minimum vertex cover size $|C| = k$. Elements whose copies lie outside $C$ form an antichain in $P$ of size at least $n - k$, completing the proof.

Proof of Mirsky via Height Levels. Define $h(x)$ as the length of the longest chain in $P$ ending at $x$. If $x < y$, appending $y$ shows $h(y) \ge h(x) + 1$. Thus, elements with equal $h(x)$ values form an antichain $A_i = \{x \in P : h(x) = i\}$. These level sets $A_1, A_2, \ldots, A_h$ partition $P$ into exactly $h(P)$ antichains.

Exercise. For $V$ with an isolated element $d$, determine both optima. Hint: $\{a,b,d\}$ is an antichain. Answer: Width is 3 ($\{a,b,d\}$) and height is 2 ($\{a,c\}$). Chain partition $\{a,c\}, \{b\}, \{d\}$ (3 chains) and antichain partition $\{a,b,d\}, \{c\}$ (2 antichains) achieve the bounds.

17.5 Distributive lattices and Birkhoff's representation theorem

Lattice Fundamentals. A lattice is a poset $L$ in which every pair $x, y \in L$ possesses:

• A unique greatest lower bound, called the meet $x \wedge y$.
• A unique least upper bound, called the join $x \vee y$.

A lattice is distributive if the operations satisfy the distributive laws for all $x, y, z \in L$:

$$ x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z), \qquad x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z). $$

For any finite poset $P$, its ideal collection $J(P)$ ordered by set inclusion forms a distributive lattice where $I \wedge K = I \cap K$ and $I \vee K = I \cup K$.

Join-Irreducible Elements. An element $j \in L$ is join-irreducible if $j \ne \hat{0}$ and $j = x \vee y \implies j = x$ or $j = y$ (it cannot be expressed as the join of strictly smaller elements). Let $Q(L)$ denote the subposet of join-irreducible elements of $L$.

Birkhoff's Representation Theorem. Every finite distributive lattice $L$ is isomorphic to the ideal lattice $J(Q)$, where $Q = Q(L)$ is the poset of join-irreducible elements of $L$ under the order inherited from $L$:

$$ L \cong J(Q(L)). $$

Proof Strategy: Define map $\phi: L \to J(Q)$ by $\phi(x) = \{j \in Q : j \le x\}$. Distributivity implies that join-irreducibles are join-prime ($j \le x \vee y \implies j \le x \text{ or } j \le y$), which guarantees that $\phi(x)$ is a valid order ideal and $\phi$ is a lattice isomorphism.

Exercise. What is $J(P)$ when $P$ is a 3-element chain? When $P$ is a 3-element antichain? Answer: For a 3-element chain, $J(P)$ is a 4-element chain. For a 3-element antichain, $J(P)$ is the 8-element Boolean lattice $B_3$.

17.6 Boolean lattices and partition lattices

Boolean Lattice $B_n$. The Boolean lattice $B_n$ consists of all subsets of $[n] = \{1, 2, \ldots, n\}$ ordered by set inclusion $\subseteq$. Meet is set intersection $\cap$, join is set union $\cup$. $B_n$ contains $2^n$ elements, has rank $n$, and contains $\binom{n}{r}$ elements at rank $r$. It has $n!$ maximal chains and is distributive ($B_n \cong J(A_n)$, where $A_n$ is an $n$-element antichain).

Partition Lattice $\Pi_n$. The partition lattice $\Pi_n$ consists of all set partitions of $[n]$, ordered by refinement: $\pi \le \sigma$ if every block of $\pi$ is contained inside a block of $\sigma$. Its least element $\hat{0} = 1|2|\cdots|n$ is the singleton partition, and its greatest element $\hat{1} = 12\cdots n$ is the single-block partition. A cover in $\Pi_n$ merges exactly two blocks, giving rank function $\rho(\pi) = n - |\pi|$ (where $|\pi|$ is the number of blocks).

Non-Distributivity of $\Pi_3$. The partition lattice $\Pi_3$ has $5$ elements: bottom $\hat{0} = 1|2|3$, three atoms $p = 12|3, q = 13|2, r = 23|1$, and top $\hat{1} = 123$. This forms the 5-element diamond lattice $M_3$. It is non-distributive because:

$$ p\wedge(q\vee r) = p\wedge \hat{1} = p, \quad \text{whereas} \quad (p\wedge q)\vee(p\wedge r) = \hat{0}\vee \hat{0} = \hat{0}. $$

Although $|J(V)| = 5$ and $|\Pi_3| = 5$, $J(V)$ is distributive while $\Pi_3$ is not. Cardinality alone does not dictate lattice structure.

Exercise. In $\Pi_3$, compute $p \wedge q$ and $p \vee q$. Compare the number of maximal chains in $\Pi_3$ and $B_3$. Answer: $p \wedge q = \hat{0}$ ($1|2|3$), $p \vee q = \hat{1}$ ($123$). $\Pi_3$ has $3$ maximal chains; $B_3$ has $6$.

17.7 Incidence algebras and generalized Möbius inversion

What & Definitions. A poset $P$ is locally finite if every interval $[x, y] = \{z \in P : x \le z \le y\}$ is finite. The incidence algebra $I(P)$ consists of all functions $\alpha(x, y)$ defined on comparable pairs $x \le y$ with values in a field (e.g., $\mathbb{Q}$). Multiplication in $I(P)$ is defined by convolution:

$$ (\alpha\ast\beta)(x,y)=\sum_{x\le z\le y}\alpha(x,z)\beta(z,y). $$

The multiplicative identity is the Kronecker delta $\delta(x,y) = 1$ if $x=y$, and $0$ otherwise.

Zeta Function and Möbius Function.

• The Zeta function $\zeta \in I(P)$ is defined by $\zeta(x,y) = 1$ for all $x \le y$.
• The Möbius function $\mu \in I(P)$ is the convolution inverse of $\zeta$ ($\mu \ast \zeta = \zeta \ast \mu = \delta$). It is defined recursively by:

$$ \mu(x,x)=1,\qquad \mu(x,y)=-\sum_{x\le z < y}\mu(x,z) \quad (x < y). $$

Generalized Möbius Inversion Theorem. Let $P$ be a finite poset, and let $f, g: P \to \mathbb{Q}$ be functions. Then:

$$ g(x)=\sum_{y\le x}f(y) \quad \forall x\in P \iff f(x)=\sum_{y\le x}g(y)\mu(y,x) \quad \forall x\in P. $$

Möbius Values for Classical Lattices:

• Boolean Lattice $B_n$: $\mu(S, T) = (-1)^{|T \setminus S|}$ for $S \subseteq T$ (recovers Inclusion–Exclusion).
• Partition Lattice $\Pi_n$: $\mu(\hat{0}, \hat{1}) = (-1)^{n-1} (n-1)!$.

Exercise. On $B_2$, let $g(S) = 2^{|S|}$. Recover $f(S)$. Hint: Use Möbius inversion on $B_2$. Answer: $f(S) = \sum_{T \subseteq S} (-1)^{|S \setminus T|} 2^{|T|} = (2-1)^{|S|} = 1$ for all $S \subseteq [2]$.

17.8 Order polynomials and order-preserving maps

What & Definitions. For a finite poset $P$ ($|P| = n$) and target size $m \in \mathbb{Z}_{\ge 0}$ (let $[m] = \{1, 2, \ldots, m\}$):

• A map $f: P \to [m]$ is weakly order-preserving if $x \le_P y \implies f(x) \le f(y)$. Its counting function is $\Omega_P(m)$.
• A map $f: P \to [m]$ is strictly order-preserving if $x <_P y \implies f(x) < f(y)$. Its counting function is $\Omega_P^\circ(m)$.

Both $\Omega_P(m)$ and $\Omega_P^\circ(m)$ are polynomials in $m$ of degree $n$, with leading coefficient $e(P) / n!$.

Order Polynomial Reciprocity Theorem (Stanley). For any finite poset $P$ of size $n$:

$$ \Omega_P(-m)=(-1)^n\Omega_P^\circ(m). $$

Worked Example for Poset $V$. Fixing $f(c) = k \in [m]$, weak preservation allows $k$ choices for $f(a)$ and $f(b)$ ($1 \le f(a), f(b) \le k$), yielding $\Omega_V(m) = \sum_{k=1}^m k^2 = \frac{m(m+1)(2m+1)}{6}$. Strict preservation allows $k-1$ choices, yielding $\Omega_V^\circ(m) = \sum_{k=1}^m (k-1)^2 = \frac{m(m-1)(2m-1)}{6}$. Evaluating $\Omega_V(-m)$ confirms reciprocity directly.

Exercise. Derive $\Omega(m)$ and $\Omega^\circ(m)$ for an $n$-element chain and an $n$-element antichain. Answer: For a chain, $\Omega(m) = \binom{m+n-1}{n}$ and $\Omega^\circ(m) = \binom{m}{n}$. For an antichain, both equal $m^n$.

17.9 P-partitions and quasisymmetric functions

What & Definitions. Fix a bijective labeling $\omega: P \to [n]$. A $(P, \omega)$-partition is a function $f: P \to \mathbb{Z}_{>0}$ satisfying two conditions for all $x <_P y$:

1. $f(x) \le f(y)$ if $\omega(x) < \omega(y)$ (weak order preservation).
2. $f(x) < f(y)$ if $\omega(x) > \omega(y)$ (strict order preservation).

The generating function $K_{P, \omega}(\mathbf{x}) = \sum_f \prod_{v \in P} x_{f(v)}$ expands in terms of Gessel's fundamental quasisymmetric functions $F_{n, D}(\mathbf{x})$:

$$ K_{P,\omega}=\sum_{\pi\in\mathcal L(P,\omega)}F_{n,\operatorname{Des}(\pi)}, $$

where $\mathcal{L}(P, \omega)$ is the set of label permutations corresponding to linear extensions of $P$, and $\operatorname{Des}(\pi)$ is the descent set of $\pi$.

Exercise. Label $a,b,c$ in $V$ by $2,3,1$. Which comparisons reverse label order? Answer: Both $a < c$ ($\omega(a)=2 > 1=\omega(c)$) and $b < c$ ($\omega(b)=3 > 1=\omega(c)$) reverse label order, forcing strict inequalities $f(a) < f(c)$ and $f(b) < f(c)$.

17.10 Shellability and Cohen–Macaulay posets

Order Complex $\Delta(P)$. The order complex $\Delta(P)$ of a poset $P$ is the simplicial complex whose vertices are elements of $P$ and whose faces are chains of $P$. Maximal chains in $P$ form the maximal faces (facets) of $\Delta(P)$. For a bounded poset $P$ with $\hat{0}$ and $\hat{1}$, we study the proper order complex $\Delta(\bar{P})$ where $\bar{P} = P \setminus \{\hat{0}, \hat{1}\}$.

Pure Shellability. A $d$-dimensional simplicial complex is pure shellable if its facets can be ordered $F_1, F_2, \ldots, F_t$ such that for each $j > 1$, the intersection $F_j \cap (\bigcup_{i=1}^{j-1} F_i)$ is a pure $(d-1)$-dimensional complex.

EL-Labelings (Edge-Lexicographic Labelings). A graded poset $P$ possesses an EL-labeling if its Hasse cover edges can be labeled such that in every interval $[x, y]$, there is a unique maximal chain with strictly increasing labels, and that chain's label sequence is lexicographically first among all maximal chains in $[x, y]$. An EL-labelable poset is guaranteed to be pure shellable and Cohen–Macaulay.

Topological Möbius Identity. For any open interval $(x, y)$ in a bounded Cohen–Macaulay poset, the Möbius value equals the reduced Euler characteristic of its proper order complex:

$$ \mu(x,y)=\widetilde\chi\bigl(\Delta((x,y))\bigr). $$

Exercise. Describe $\Delta(\bar{\Pi}_3)$ and compute its reduced Euler characteristic. Answer: $\Delta(\bar{\Pi}_3)$ consists of 3 isolated vertices ($12|3, 13|2, 23|1$). It is a pure 0-dimensional complex with $3$ vertices and $0$ edges. Its reduced Euler characteristic is $V - E - 1 = 3 - 0 - 1 = 2$, agreeing with $\mu(\hat{0}, \hat{1}) = 2$.

Count linear extensions and compare lattice structures

Dependency orders connect scheduling to algebra and topology. Linear extensions count legal sequential schedules; ideals record legal completed states. A maximal chain of the ideal lattice follows one complete schedule, while the proper-part order complex organizes compatible intermediate states into faces. Shellability concerns how those maximal-chain faces fit together, adding information beyond a schedule count.

The investigation compares a chain, independent tasks, and the running dependency poset. It then contrasts a distributive ideal lattice with a nondistributive partition lattice of the same cardinality. Exact finite enumeration checks the examples; the bijections and lattice proofs explain why the relationships persist beyond those examples.