Greene-Kleitman theorem
From Egres Open
Theorem (Greene-Kleitman [1]). Let [math](V,\leq)[/math] be a partially ordered finite set, and let k be a positive integer. Then the maximum size of the union of k antichains equals the minimum of [math]\sum_{C \in \Pi} \min\{|C|,k\}[/math] taken over all partitions [math]\Pi[/math] of V into chains.
An immediate corollary is the following: if X is a maximum size union of k antichains, and [math]\Pi[/math] is a chain partition that minimizes [math]\sum_{C \in \Pi} \min\{|C|,k\},[/math] then every chain [math]C \in \Pi[/math] contains exactly [math]\min\{|C|,k\}[/math] elements from X.
