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
Mirsky's theorem
Summary
In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.
The height of a partially ordered set is defined to be the maximum cardinality of a chain, a totally ordered subset of the given partial order. For instance, in the set of positive integers from 1 to N, ordered by divisibility, one of the largest chains consists of the powers of two that lie within that range, from which it follows that the height of this partial order is .
Mirsky's theorem states that, for every finite partially ordered set, the height also equals the minimum number of antichains (subsets in which no pair of elements are ordered) into which the set may be partitioned. In such a partition, every two elements of the longest chain must go into two different antichains, so the number of antichains is always greater than or equal to the height; another formulation of Mirsky's theorem is that there always exists a partition for which the number of antichains equals the height. Again, in the example of positive integers ordered by divisibility, the numbers can be partitioned into the antichains {1}, {2,3}, {4,5,6,7}, etc. There are sets in this partition, and within each of these sets, every pair of numbers forms a ratio less than two, so no two numbers within one of these sets can be divisible.
To prove the existence of a partition into a small number of antichains for an arbitrary finite partially ordered set, consider for every element x the chains that have x as their largest element, and let N(x) denote the size of the largest of these x-maximal chains.
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.