Greene-Kleitman theorem

2020 Mathematics Subject Classification: Primary: 06A06 [MSN][ZBL]

Dilworth's theorem [a1] states that in a finite partially ordered set the 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 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 [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 [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 [a2].

References

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