Some sequences associated with combinatorial structures

Greene and Kleitman generalized Dilworth's decomposition theorem for partially ordered sets by characterizing, for each k, the size of the largest k-family of a partially ordered set. This was used by Greene to show that two sequences associated with any finite poset P are conjugate partitions of the integer ∥P∥. A natural context for stating and proving such results is introduced here. A generalization of these theorems to acyclic digraphs is proved and applied to prove the acyclic case of a conjecture of Berge. An analog of Greene's theorem is proved for matchings of a bipartite graph, answering a question of Albertson.