Greene-Kleitman theorem

Dilworth's theorem [a1] states that in a finite partially ordered set the maximal size of an independent set (i.e., a set of mutually incomparable elements) is equal to the minimal number of chains needed to cover the partially ordered set (a chain is a set of mutually comparable elements).

C. Greene and D.J. Kleitman asked what happens if in the statement of this theorem the notion of an "independent set" is replaced by the more general notion of "union of k-independent sets" , also called a -independent set. Suppose that are independent sets. If is a partition of the graph into chains, then each meets in at most points. Hence (the right-hand side of this inequality is called the -norm of ). The analogue of Dilworth's theorem, which is the Greene–Kleitman theorem [a4], is that this trivial bound can, in fact, be attained: The maximal size of a -independent set in a partially ordered set is the minimal -norm of a partition of the partially ordered set into chains.

Dilworth's theorem has an easy "dual" version: In any partially ordered set the minimal number of independent sets needed to cover all vertices is equal to the maximal size of a chain in the partially ordered set (just take the covering system of independent sets to be the levels of the partially ordered set, where a level is the set of all vertices of a given height). This theorem, too, has a "k-analogue" , proven by Greene [a3]. Let a -chain be defined as a union of chains, and take the -norm of a partition of the partially ordered set into independent sets to be .

Then (Greene's theorem): The maximal size of a -chain is equal to the minimal -norm of a partition into independent sets.

An elegant proof for both these results simultaneously is given in [a2].

References

[a1]	R.P. Dilworth, "A decomposition theorem for partially ordered sets" Ann. of Math. , 51 (1950) pp. 161–166
[a2]	A. Frank, "On chain and antichain families of a partially ordered set" J. Combin. Th. B , 29 (1980) pp. 176–184
[a3]	C. Greene, "Some partitions associated with a partially ordered set" J. Combin. Th. A , 20 (1976) pp. 69–79
[a4]	C. Greene, D.J. Kleitman, "The structure of Sperner -families" J. Combin. Th. A , 20 (1976) pp. 41–68