View source for Greene-Kleitman theorem

Dilworth's theorem [[#References|[a1]]] states that in a finite [[Partially ordered set|partially ordered set]] the [[Width of a partially ordered set|width]], the maximal size of an independent set (i.e., an [[anti-chain]], 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, a [[totally ordered set|totally ordered subset]]).

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102202.png" />-independent set. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102203.png" /> are independent sets. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102204.png" /> is a partition of the [[Graph|graph]] into chains, then each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102205.png" /> meets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102206.png" /> in at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102207.png" /> points. Hence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g1102208.png" /> (the right-hand side of this inequality is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022010.png" />-norm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022011.png" />). The analogue of Dilworth's theorem, which is the Greene–Kleitman theorem [[#References|[a4]]], is that this trivial bound can, in fact, be attained: The maximal size of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022012.png" />-independent set in a partially ordered set is the minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022013.png" />-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 [[#References|[a3]]]. Let a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022015.png" />-chain be defined as a union of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022016.png" /> chains, and take the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022017.png" />-norm of a partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022018.png" /> of the partially ordered set into independent sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022019.png" /> to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022020.png" />.

Then (Greene's theorem): The maximal size of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022021.png" />-chain is equal to the minimal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g110/g110220/g11022022.png" />-norm of a partition into independent sets.

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

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.P. Dilworth,   "A decomposition theorem for partially ordered sets"  ''Ann. of Math.'' , '''51'''  (1950)  pp. 161–166  {{ZBL|0038.02003}}</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  A. Frank,   "On chain and antichain families of a partially ordered set"  ''J. Combin. Th. B'' , '''29'''  (1980)  pp. 176–184  {{ZBL|0443.06003}}</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  C. Greene,   "Some partitions associated with a partially ordered set"  ''J. Combin. Th. A'' , '''20'''  (1976)  pp. 69–79  {{ZBL|0323.06002}}</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Greene,   D.J. Kleitman,   "The structure of Sperner $k$-families"  ''J. Combin. Th. A'' , '''20'''  (1976)  pp. 41–68  {{ZBL|0355.05027}}</TD></TR>
</table>