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

Mark Dukes ; Vít Jelínek ; Martina Kubitzke

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

In this paper we present a bijection between composition matrices and ($\mathbf{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 ($\mathbf{2+2}$)-free posets. Chains in a ($\mathbf{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 ($\mathbf{2+2}$)- and ($\mathbf{3+1}$)-free by certain properties of their associated composition matrices.

Détail

DOI : 10.37236/531

Classification : 05A19, 06A07
Mots-clés : \((2+2)\)-free poset, dual poset, bijection, interval orders, composition matrix