View source for Greene-Kleitman theorem

{{TEX|done}}{{MSC|06A06}}

[[Dilworth theorem|Dilworth's theorem]] [[#References|[a1]]] states that in a finite [[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 $k$-independent set. Suppose that $A_1,\ldots,A_k$ are independent sets. If $\mathcal{C}=\{C_1,\ldots,C_m\}$ is a partition of the set into chains, then each $C_i$ meets $\cup_{j\le k}A _j$ in at most $\min(|C_i|,k)$ points. Hence 
$$
\left\vert \cup_{j\le k} A_j \right\vert \le \sum_{i\le m} \min(|C_i|,k)
$$
(the right-hand side of this inequality is called the $k$-norm of $\mathcal{C}$). 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 $k$-independent set in a partially ordered set is the minimal $k$-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 $k$-chain be defined as a union of $k$ chains, and take the $k$-norm of a partition $\mathcal{P}$ of the partially ordered set into independent sets $I_1,\ldots,I_m$ to be $\sum_{j\le m}\min(|I_j|,k)$.

Then (Greene's theorem): The maximal size of a $k$-chain is equal to the minimal $k$-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>