Skip to main content
3 of 3
Human-readable references
David Roberts
  • 35.5k
  • 11
  • 124
  • 349

Greene's theorem

Curtis Greene, Some partitions associated with a partially ordered set, Journal of Combinatorial Theory Series A, Vol.20(1) (1976) pp 69–79, doi:10.1016/0097-3165(76)90078-9

and the Greene-Kleitman theorem

Curtis Greene, Daniel J Kleitman, The structure of sperner $k$-families, Journal of Combinatorial Theory Series A, Vol.20(1) (1976) pp 41–68, doi:10.1016/0097-3165(76)90077-7

are remarkably deep theorems that hold for any finite partially ordered set.

Greene's theorem. Let $P$ be an $n$-element poset. Let $\lambda_1+\cdots+\lambda_k$ be the largest size of a union of $k$ chains of $P$. Let $\mu_1+\cdots+\mu_k$ be the largest size of a union of $k$ antichains. Let $\lambda=(\lambda_1,\lambda_2,\dots)$ and $\mu=(\mu_1,\mu_2,\dots)$. Then $\lambda$ and $\mu$ are conjugate partitions, i.e., they are weakly decreasing, and the Young diagram of $\mu$ is the transpose of that of $\lambda$.

To see the subtlety of this result, there is for instance a nine-element poset with $\lambda=(5,3,1)$, but $P$ is not a union of a 5-element chain and a 3-element chain.

The fact that $\mu_1$ is the number of parts of $\lambda$ is Dilworth's theorem: the size of the largest antichain of $P$ is equal to the least number of chains whose union is $P$.

Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279