Motivation
A partial order records which objects can follow which, while leaving some pairs incomparable. If its elements must be arranged into ordered tracks, how many tracks are necessary? Every antichain supplies an obstruction: its elements cannot share a track. Dilworth's theorem says that in a finite poset this obvious obstruction is the only one.
The proof will turn compatible consecutive choices into matching edges. A matching chooses at most one predecessor and one successor for each element. A minimum vertex cover then reveals a largest antichain. The construction gives both an arrangement and a certificate that fewer tracks are impossible, so the conclusion is more useful than an unexplained equality of two numbers.
Definitions
Definition 6.2.1
(Chains, antichains, height and width)
Let be a finite partially ordered set. A chain is a subset whose elements are pairwise comparable. An antichain is a subset whose distinct elements are pairwise incomparable. The height is the largest chain size, and the width is the largest antichain size. A chain partition expresses as a disjoint union of nonempty chains; an antichain partition uses nonempty antichains. For the empty poset, height, width and both minimum partition sizes are zero.
A partition is different from one long chain or one large antichain: it must account for every element exactly once. Any antichain meets each chain in at most one element. Therefore its size bounds the number of parts in every chain partition from below. Likewise every chain gives a lower bound for the size of an antichain partition.
Definition 6.2.2
(The bipartite strict-comparison graph)
Make two separate copies of . Join to exactly when in the original poset. The two copies of one element are distinct vertices, and there is no edge . The graph uses every strict comparison, including comparisons implied by transitivity.
A matching is a collection of edges with disjoint endpoints; its maximum size is denoted . A vertex cover meets every graph edge. These graph definitions refer to the two-copy graph, whereas chains and antichains consist of original poset elements. Keeping that distinction explicit prevents double-counting the two copies.
Theorem/Proposition
Lemma 6.2.3
(Matchings and vertex covers in a bipartite graph)
In every finite bipartite graph, the largest size of a matching equals the smallest size of a vertex cover.
Theorem 6.2.4
(Dilworth's finite chain-partition theorem)
For every finite poset , the smallest number of chains in a partition of equals . More precisely, for and maximum matching size in the strict-comparison graph, both quantities equal . A maximum matching and an equal-size vertex cover construct an optimal chain partition and a maximum antichain.
Theorem 6.2.5
(The height version: antichain partitions)
For every finite poset , the smallest number of antichains in a partition equals . For nonempty , define as the maximum size of a chain ending at . The nonempty level sets of form an optimal antichain partition.
The two statements exchange the roles of chains and antichains in a partition problem. The height theorem has a short direct proof; the width theorem requires a more substantial argument. Reversing the order relation alone does not exchange chains with antichains, since it leaves comparability unchanged.
Proof sketch or proof idea
Proof
(Matchings and covers in a bipartite graph)
We first justify the bipartite matching–cover fact used in the proof. Take a maximum matching in any finite bipartite graph with parts . Start at the unmatched left vertices , follow unmatched edges from left to right and matched edges from right to left, and let be the reachable vertices in the two parts. No unmatched right vertex is reachable, because the resulting alternating path could increase the matching size.
Every reached right vertex is matched to a reached left vertex, and every reached left vertex outside was reached through its matched edge. Thus the matching pairs with . Also every neighbor of a reached left vertex is reached: an unmatched edge can be followed, while its matched neighbor, if any, is its predecessor in the search. Hence
covers every edge, and , the matching size. Every cover has at least the size of every matching because disjoint matching edges need distinct covering vertices. This proves the required matching–cover equality, including empty graphs.
Proof
(Chains from a matching, an antichain from a cover)
Now use a maximum matching in the strict-comparison graph. Replace each matched edge by a directed link on original elements. Each element has at most one outgoing and one incoming link. There is no directed cycle, since a cycle of strict order relations would contradict transitivity and irreflexivity. The links therefore form disjoint directed paths, with isolated vertices allowed. Each path is a chain, and the number of paths is .
Conversely, a chain partition into parts supplies matching edges between consecutive elements within each chain. A chain of size supplies edges, so together there are edges. Left and right copies impose exactly the required predecessor and successor restrictions. Thus , proving that is the minimum chain-partition size.
Choose a vertex cover of size in the two-copy graph and set
If two elements of were comparable, their corresponding comparison edge would be uncovered. Therefore is an antichain. At most different original labels have a copy in , so . The constructed chain partition gives the opposite bound for every antichain. Consequently , proving Dilworth's theorem. We did not assume the cover contains at most one copy of each label; the counting inequality and opposite bound are sufficient.
Proof X-ray
A partition and an obstruction meeting at one number
Two independent constructions meet. The matching produces a chain partition with parts; what makes the links form paths is that a matching uses each left copy and each right copy at most once, so the two-copy device is exactly the rule “at most one successor, at most one predecessor”, while irreflexivity and transitivity exclude directed cycles. The cover produces an antichain of size at least ; the key move is to exclude a label as soon as either copy is covered, so that any comparison inside would leave the edge uncovered. Neither construction alone proves optimality. The bipartite lemma enters only through , and that is what makes the counts coincide: the antichain has at least elements, and its elements lie in different chains of the partition, so it has at most . Transitivity is used twice: to exclude cycles, and to put every comparison into the graph, without which consecutive elements of a chain need not be joined by an edge.
Proof
(Rank levels form an optimal antichain partition)
For the height theorem, if , append to a longest chain ending at . This gives . Equal-rank elements are therefore incomparable. The level sets partition the poset into at most antichains. A chain of size requires at least that many antichain parts, so the partition is optimal. The empty case follows from the conventions.
Worked examples
Worked example 6.2.6
(One predecessor and two incomparable successors)
Let and , with incomparable. The comparison graph has edges , so . A matching using gives chains . The cover leaves both copies of outside, giving maximum antichain . Thus width is two. The rank levels are and , an optimal antichain partition of size two, also the height.
Worked example 6.2.7
(Divisors of twelve provide both certificates)
Order by divisibility. The chains and give a two-part partition; is an antichain, proving width two. The corresponding matching has edges . The cover meets every strict-divisibility edge and has the same size four. Its uncovered original labels are precisely four and six. A longest chain has size four, so the height theorem instead needs four antichain parts.
Worked example 6.2.8
(Cover edges alone give the wrong optimization problem)
Take five elements with , , , and all transitive comparisons. Width is two: and are chains, and is an antichain. Using only Hasse cover edges gives maximum matching size two, because at most one link can enter and at most one can leave it. The erroneous formula would then give three chains. Including the comparison supplies a matching of size three and the correct answer two. A chain need not use every element lying between two of its members.
Extracting the actual partition
The proof describes a concrete reconstruction. For every original element, record its matched successor and matched predecessor, if present. Start a chain at each element with no matched predecessor and repeatedly follow its successor until none remains. Every element appears in exactly one such path. Acyclicity ensures a starting point exists in each component, and the degree restrictions prevent branching or merging.
The two copies allow an internal chain element to have both a predecessor and a successor. They do not allow two predecessors: those would use the same right-copy vertex in two matching edges. Two successors would similarly reuse a left-copy vertex. Matching is therefore enforcing a path constraint, rather than requiring that original elements appear in only one link altogether.
The antichain reconstruction uses the opposite perspective. An original label is selected only when neither of its copies is in the cover. Selecting a label merely because its left copy is uncovered would not suffice: a comparison edge might then be covered at the right copy of another selected label. Both-copy exclusion is the precise property making comparability impossible.
Width and height constrain total size
An optimal chain partition has width many parts, each of size at most the height. Hence
This bound does not identify the individual chains, but it often gives an immediate obstruction. If a poset has more than nine elements, its height and width cannot both be at most three. Equality is possible, for instance with three mutually incomparable chains of length three.
An application concerns a sequence of distinct real numbers. Order its indices by declaring when , or when and the value at index is smaller. Chains are increasing subsequences. Antichains, read in index order, are decreasing subsequences because the values are distinct. If the sequence has terms, it cannot have both all increasing subsequences of length at most and all decreasing subsequences of length at most . Otherwise the size bound would give at most terms. Thus one of the corresponding longer subsequences must occur.
The distinctness hypothesis explains the strict inequalities. With repeated values, an incomparable pair in index order may have equal rather than decreasing values. One can formulate related nonstrict variants, but they require a chosen tie convention and should not be inferred unchanged from the distinct-value argument.
Concept lensStructural
Height and width describe different obstructions
A long chain forces many antichain parts. A wide antichain forces many chain parts. A Hasse diagram's drawn height or row lengths need not equal either quantity. The partition theorems refer to comparability and certified extrema, not to where a drawing happens to place its vertices.
What the rank levels compute
The rank used in the height proof is the size of a largest chain ending at an element, not an arbitrary label in a picture. Along a linear extension, compute it as one plus the largest rank of a strict predecessor, using zero when there are none. Every predecessor is already available. This supplies the antichain levels and a longest-chain certificate by remembering a predecessor attaining each maximum.
A poset need not be graded: different maximal chains may have different lengths. The longest-chain rank still works because only the strict-increase property is needed. No assumption that every cover raises rank by exactly one entered the proof. Imposing that stronger condition would unnecessarily exclude valid examples.
Common mistakes
Counterexample mode
Interchanging height and width changes the problem
A four-element total order has width one and height four. It needs one chain part but four antichain parts. Reversing its order does not change either value: it still has all pairs comparable. The corrected statements pair minimum chain partitions with width and minimum antichain partitions with height; they are not obtained by swapping words without a new proof.
Common mistake
(Hasse edges instead of all strict comparisons)
Do not replace the strict-comparison graph by the Hasse edges without justification. For the five-element poset with , , , , the Hasse edges admit a matching of size only two, so would report three chains, while the comparison yields a matching of size three and the true answer two. Consecutive elements of a chain in a partition need not form a cover relation.
Common mistake
(Fewest chains is not the longest chain)
The minimum number of chain parts must account for every element and is controlled by width; the maximum size of one chain is the height. Among the divisors of , the longest chain has four elements, yet the two chains and already partition the poset.
Summary
A bipartite matching encodes consecutive chain links, while a minimum cover exposes an antichain of the same required partition size. This proves Dilworth's theorem constructively. Longest-ending-chain ranks give the complementary antichain partition theorem and lead to useful size and subsequence bounds.
Exercises
Quick check
(For the subset poset on a three-element ground set, give a partition into three chains and a three-element antichain proving optimality.)
Every subset, including the empty set, must occur exactly once in the partition.
Solution · Answer
On ground set , use chains , and . These disjoint chains contain all eight subsets. The three singletons form an antichain, so at least three chains are required. The displayed partition attains that bound.
Quick check
(For the five-element poset with , , , , find the rank levels and a longest chain. Compare the two partition theorems.)
Include all comparisons forced by transitivity.
Solution · Answer
The ranks are one on , two on , and three on . Their level sets give three antichain parts. A longest chain is , proving height three. The two chains and antichain prove width two and a minimum chain partition of size two. The two optimal partition counts legitimately differ.
Quick check
(Prove that any sequence of ten distinct real numbers has an increasing subsequence of length four or a decreasing subsequence of length four.)
Specify the index poset and apply the proved size bound.
Solution · Answer
Order indices by simultaneous increase of index and value, including equality for reflexivity. Transitivity and antisymmetry follow from the two strict inequalities. If neither required subsequence existed, every chain and antichain would have size at most three: distinctness makes an antichain decrease when read in index order. The bound would give ten at most nine, a contradiction. Thus at least one stated subsequence exists.