Every finite partially ordered set can be partitioned into as many chains in a partial order as its largest antichain. Reachability in an acyclic directed graph is a partial order, so the theorem supplies chains which can be expanded into directed paths, possibly overlapping at intervening vertices.
Articles by others on the same topic
Dilworth's theorem is a result in order theory, a branch of mathematics that studies the properties of ordered sets. The theorem states that in any finite partially ordered set (poset), the size of the largest antichain (a subset of elements in which no two elements are comparable) is equal to the smallest number of chains (totally ordered subsets) that can cover the poset. In more formal terms: - Let \( P \) be a finite poset.