Mirsky's theorem

From Wikipedia, the free encyclopedia

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 Leon Mirsky (1971) 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 theorem

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 $1+\lfloor \log _{2}N\rfloor$ .

Mirsky's theorem states that, for every 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 $1+\lfloor \log _{2}N\rfloor$ 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. Then each set N⁻¹(i), consisting of elements that have equal values of N, is an antichain, and these antichains partition the partial order into a number of antichains equal to the size of the largest chain. In his original proof, Mirsky constructs the same partition inductively, by choosing an antichain of the maximal elements of longest chains, and showing that the length of the longest chain among the remaining elements is reduced by one.

Relation to Dilworth's theorem

Mirsky was inspired by Dilworth's theorem, stating that, for every partially ordered set, the maximum size of an antichain equals the minimum number of chains in a partition of the set into chains. For sets of order dimension two, the two theorems coincide (a chain in the majorization ordering of points in general position in the plane is an antichain in the set of points formed by a 90° rotation from the original set, and vice versa) but for more general partial orders the two theorems differ, and (as Mirsky observes) Dilworth's theorem is more difficult to prove.

Mirsky's theorem and Dilworth's theorem are also related to each other through the theory of perfect graphs. An undirected graph is perfect if, in every induced subgraph, the chromatic number equals the size of the largest clique. In the comparability graph of a partially ordered set, a clique represents a chain and a coloring represents a partition into antichains, and induced subgraphs of comparability graphs are themselves comparability graphs, so Mirsky's theorem states that comparability graphs are perfect. Analogously, Dilworth's theorem states that every complement graph of a comparability graph is perfect. The perfect graph theorem of Lovász (1972) states that the complements of perfect graphs are always perfect, and can be used to deduce Dilworth's theorem from Mirsky's theorem and vice versa (Golumbic 1980).

Relation to the Gallai–Hasse–Roy–Vitaver theorem

Mirsky's theorem can be restated in terms of directed acyclic graphs (representing a partially ordered set by reachability of their vertices), as the statement that there exists a graph homomorphism from a given directed acyclic graph G to a k-vertex transitive tournament if and only if there does not exist a homomorphism from a (k + 1)-vertex path graph to G. For, the largest path graph that has a homomorphism to G gives the longest chain in the reachability ordering, and the sets of vertices with the same image in a homomorphism to a transitive tournament form a partition into antichains. This statement generalizes to the case that G is not acyclic, and is a form of the Gallai–Hasse–Roy–Vitaver theorem on graph colorings and orientations (Nešetřil & Ossona de Mendez 2012).

Relation to the Erdős–Szekeres theorem

It follows from either Dilworth's theorem or Mirsky's theorem that, in every partially ordered set of rs + 1 elements, there must exist either a chain of r + 1 elements or an antichain of s + 1 elements. Mirsky (1971) uses this observation, applied to a partial order of order dimension two, to prove the Erdős–Szekeres theorem that in every sequence of rs + 1 totally ordered elements there must exist either a monotonically increasing subsequence of r + 1 elements or a monotonically decreasing subsequence of s + 1 elements.

Extensions

Mirsky's theorem extends immediately to infinite partially ordered sets with finite height. However, the relation between the length of a chain and the number of antichains in a partition into antichains does not extend to infinite cardinalities: for every infinite cardinal number κ, there exist partially ordered sets that have no infinite chain and that do not have an antichain partition with κ or fewer antichains (Schmerl 2002).

References

Dilworth, Robert P. (1950), "A Decomposition Theorem for Partially Ordered Sets", Annals of Mathematics 51 (1): 161–166, doi:10.2307/1969503, JSTOR 1969503 .
Golumbic, Martin Charles (1980), "5.7. Coloring and other problems on comparability graphs", Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press, pp. 132–135, ISBN 0-12-289260-7, MR 562306 .
Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4 .
Mirsky, Leon (1971), "A dual of Dilworth's decomposition theorem", American Mathematical Monthly 78 (8): 876–877, doi:10.2307/2316481, JSTOR 2316481 .
Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058 .
Schmerl, James H. (2002), "Obstacles to extending Mirsky's theorem", Order 19 (2): 209–211, doi:10.1023/A:1016541101728, MR 1922918 .

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.