Chains and Antichains

Chains and antichains are not a museum piece confined to poset theory; they surface wherever "comparability" models a real constraint.

Scheduling and project management. In a task-dependency graph (a poset where $x \le y$ means "task $x$ must finish before task $y$ starts"), a chain is a sequence of tasks forced into strict order, and an antichain is a set of tasks that could run in parallel with no dependency conflicts. The width of the poset is exactly the minimum number of parallel "workers" or processors needed if tasks in an antichain may run simultaneously — a direct real-world reading of Dilworth's Theorem.

Combinatorics of Young tableaux and the RSK correspondence. In the study of permutations, the longest increasing subsequence and longest decreasing subsequence of a sequence correspond exactly to the longest chain and longest antichain in an associated poset (points in the plane ordered coordinatewise). The Erdős–Szekeres theorem is a direct corollary of the chain/antichain product bound: any sequence of more than $rs$ distinct numbers contains an increasing subsequence of length $r+1$ or a decreasing subsequence of length $s+1$.

Cryptography and access control. Role-based and lattice-based access control models represent permission hierarchies as posets; an antichain of roles represents mutually non-dominating privilege levels, while chains capture strict escalation paths — width bounds the number of independent "clearance tracks" a system must support.

Statistics and multivariate ordering. Pareto-optimality in multi-objective optimization is precisely the notion of an antichain in the product order on outcome vectors: the "Pareto frontier" is a maximal antichain, and its size measures the genuine diversity of non-dominated trade-offs.

Coding theory and extremal set theory. Sperner's theorem, computing the width of the Boolean lattice $2^{[n]}$ (shown to equal $\binom{n}{\lfloor n/2\rfloor}$), is a direct width computation in the sense defined here, and underlies bounds in extremal combinatorics and coding theory involving antichains of subsets.

Ask the tutor: How does the proof of Dilworth's Theorem differ in difficulty from the proof of Mirsky's Theorem given here, and why does the "easy" chain-covering direction fail to have an equally short argument?

Picture a Hasse diagram: elements are dots, and an edge is drawn upward from $x$ to $y$ whenever $y$ covers $x$ (i.e. $x < y$ with nothing strictly between). A chain is any path you can trace by repeatedly moving upward through the diagram, possibly skipping levels — it is a "staircase" of mutually comparable elements. An antichain, by contrast, is a set of elements you could draw as a horizontal slice: none reachable from another by moving only upward or only downward. The key subtlety is that a horizontal level of a Hasse diagram (elements at the same height above the minimum) is always an antichain, but the converse fails: an antichain can zig-zag across several levels, so long as no two chosen elements are joined by any upward path at all. This is exactly what makes width a genuinely global invariant, not something read off level-by-level.

Here $P$ is the power set of $\{a,b,c\}$ ordered by inclusion — a standard example built from Partially Ordered Sets itself. The bold path $\varnothing \subset \{a\} \subset \{a,b\} \subset \{a,b,c\}$ is a chain of size $4$, so $h(P) = 4$ (no larger chain exists, since $|P|$'s ranks only go from size $0$ to size $3$, giving $4$ ranks). The middle level $\{a,b\},\{a,c\},\{b,c\}$ is an antichain of size $3$; one checks directly that no 4-element subset of $P$ is pairwise incomparable, so $w(P) = 3$.

This corollary is the easy half of the identity that Dilworth's Theorem completes: it shows a cover by $t$ chains always gives an upper bound $w(P) \le t$, and dually a cover by $r$ antichains gives $h(P) \le r$ (which Mirsky's theorem shows is tight for the antichain direction). Dilworth's theorem asserts the chain direction is also always tight: the minimum number of chains needed to cover $P$ equals $w(P)$ exactly, not merely bounds it from above.

Example 1: Divisibility poset on $\{1, 2, \dots, 30\}$. Let $P = \{1, 2, \dots, 30\}$ ordered by divisibility: $x \le y$ iff $x \mid y$. Height. A chain is a sequence of numbers each dividing the next. Consider

This is a chain of size $5$ (all terms lie in $\{1,\dots,30\}$, since $32 > 30$ is excluded). Could there be a longer chain? Any chain $x_1 \mid x_2 \mid \cdots \mid x_k$ with $x_1 \ge 1$ satisfies $x_{i+1} \ge 2 x_i$ whenever $x_{i+1} \ne x_i$ (since a proper multiple of $x_i$ is at least $2x_i$), so a strictly increasing chain of length $k$ starting at $1$ has $x_k \ge 2^{k-1}$. Requiring $x_k \le 30$ forces $2^{k-1} \le 30$, i.e. $k \le 5$ (since $2^4 = 16 \le 30 < 32 = 2^5$). Hence $h(P) = 5$. Width. Consider the set of integers in $(15, 30]$, i.e. $A = \{16, 17, \dots, 30\}$, of size $15$. If $x, y \in A$ with $x \ne y$ and $x \mid y$, then $y \ge 2x > 30$, impossible since $y \le 30$. So $A$ is an antichain of size $15$. Is there a larger one? By Mirsky's theorem in reverse — or directly — one can partition $P$ into $5$ antichains matching the "highest power of 2 dividing the odd part's chain position" stratification, but a cleaner argument: every integer $n\in\{1,\ldots,30\}$ can be written uniquely as $n = 2^{a}\,m$ with $m$ odd; group by the odd part $m$. Each group $\{m, 2m, 4m, \dots\} \cap P$ is a chain (all terms are comparable via divisibility, forming a chain of consecutive powers of $2$ times $m$). The odd numbers in $\{1,\dots,30\}$ are $1,3,5,\dots,29$, giving exactly $15$ such chains, and they partition $P$ (every integer has a unique odd part). By the corollary above, covering $P$ by $15$ chains gives $w(P) \le 15$. Combined with the antichain $A$ of size $15$ exhibited above, $w(P) = 15$ exactly.

Example 2: Subsets of $\{1,2,3,4\}$ ordered by inclusion, restricted to sizes $0,1,3,4$ only (an asymmetric sub-poset). Let $Q$ consist of all subsets of $\{1,2,3,4\}$ of size $0$, $1$, $3$, or $4$ (sizes $2$ deliberately omitted), ordered by inclusion. Concretely:

so $|Q| = 1 + 4 + 4 + 1 = 10$. Height. A maximal chain must go $\varnothing \subset \{i\} \subset T \subset \{1,2,3,4\}$ where $T$ is a $3$-element set containing $i$. For instance $\varnothing \subset \{1\} \subset \{1,2,3\} \subset \{1,2,3,4\}$ is a valid chain (each inclusion strict and holds), of size $4$. Since ranks in $Q$ only take values $0,1,3,4$ (four distinct rank values), no chain can have more than $4$ elements — each element of a chain must have a distinct rank (comparable, unequal sets under inclusion have different sizes), and only $4$ rank values are present. So $h(Q) = 4$. Width. The size-$1$ singletons $\{1\},\{2\},\{3\},\{4\}$ form an antichain of size $4$ (no singleton contains another). Likewise the four $3$-sets form an antichain of size $4$. Can we do better, e.g. mixing singletons and triples? Check $\{1\}$ against $\{2,3,4\}$: is $\{1\} \subseteq \{2,3,4\}$? No. Is $\{2,3,4\} \subseteq \{1\}$? No. They're incomparable! In fact $\{i\} \subseteq T$ (for a $3$-set $T$) happens iff $i \in T$, and each $3$-set omits exactly one element of $\{1,2,3,4\}$, so $\{i\} \subseteq T$ fails only when $T$ is the unique $3$-set omitting $i$. So pick, for each singleton $\{i\}$, the $3$-set $T_i$ that omits $i$: then $\{i\} \not\subseteq T_i$ and $T_i \not\subseteq \{i\}$ (as $|T_i|=3>1$), so $\{i\}$ and $T_i$ are incomparable. Concretely take

matched so that $\{i\}$ pairs with the $3$-set omitting $i$ — but we must check all cross pairs, not just matched ones. Take $\{1\}$ and $\{1,2,3\}$: here $1 \in \{1,2,3\}$, so $\{1\} \subseteq \{1,2,3\}$ — comparable! So the full union $B$ of all $4$ singletons and all $4$ triples is not an antichain; only a careful mixed selection can work, and in fact no such 8-element mix is antichain since each singleton is contained in exactly three of the four triples (all except the one it's excluded from), giving many comparable cross-pairs. Testing shows the largest antichain stays at size $4$: any antichain containing a singleton $\{i\}$ can include at most the one triple avoiding $i$ (all three others contain $i$), and one checks by exhaustion over the $\binom{10}{5}$ candidate $5$-subsets that no $5$-element antichain exists (adding a fifth element to either all-singletons or all-triples always creates a containment, since $\varnothing$ and the full set are comparable to everything, and mixing singleton/triple pairs beyond one clash quickly forces comparability by the pigeonhole argument on the $4$ excluded elements). Hence $w(Q) = 4$.