Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Dilworth's theorem
Summary
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician .
An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. A chain decomposition is a partition of the elements of the order into disjoint chains. Dilworth's theorem states that, in any finite partially ordered set, the largest antichain has the same size as the smallest chain decomposition. Here, the size of the antichain is its number of elements, and the size of the chain decomposition is its number of chains. The width of the partial order is defined as the common size of the antichain and chain decomposition.
A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.
The following proof by induction on the size of the partially ordered set is based on that of .
Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of .
By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size . Clearly, for . For , let be the maximal element in that belongs to an antichain of size in , and set .
We claim that is an antichain.
Let be an antichain of size that contains . Fix arbitrary distinct indices and . Then . Let . Then , by the definition of . This implies that , since . By interchanging the roles of and in this argument we also have . This verifies that is an antichain.
We now return to . Suppose first that for some . Let be the chain .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.