Composition matrices, (2+2)-free posets and their specializations

Mark Dukes, Vit Jelínek, Martina Kubitzke

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


In this paper we present a bijection between composition matrices and (2 + 2)-
free posets. This bijection maps partition matrices to factorial posets, and induces a bijection from upper triangular matrices with non-negative entries having no rows or columns of zeros to unlabeled (2 + 2)-free posets. Chains in a (2 + 2)-free poset are shown to correspond to entries in the associated composition matrix whose hooks satisfy a simple condition. It is shown that the action of taking the dual of a poset corresponds to reflecting the associated composition matrix in its anti-diagonal. We further characterize posets which are both (2 + 2)- and (3 + 1)-free by certain properties of their associated composition matrices.
Original languageEnglish
Article numberP44
Number of pages9
JournalThe Electronic Journal of Combinatorics
Issue number1
Publication statusPublished - 2011


  • bijection
  • (2+2)-free poset
  • composition matrix
  • interval orders
  • dual poset

Cite this