Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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

Dukes, Mark and Jelínek, Vit and Kubitzke, Martina (2011) Composition matrices, (2+2)-free posets and their specializations. The Electronic Journal of Combinatorics, 18 (1).

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

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.

Item type: Article
ID code: 34523
Keywords: bijection, (2+2)-free poset, composition matrix, interval orders, dual poset, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 18 Oct 2011 12:49
    Last modified: 12 Jul 2012 11:56
    URI: http://strathprints.strath.ac.uk/id/eprint/34523

    Actions (login required)

    View Item