Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Composition matrices, (2 + 2)-free posets and their specializations. | Composition matrices 2 2 -free posets and their specializations Mark Dukes Department of Computer and Information Sciences University of Strathclyde Glasgow UK Vit Jelinek Fakultat fur Mathematik Universitat Wien Nordbergstrafie 15 A-1090 Vienna Austria jelinek@ Martina Kubitzke Fakultuat fuur Mathematik Universituat Wien Nordbergstrafie 15 A-1090 Vienna Austria Submitted Oct 6 2010 Accepted Feb 7 2011 Published Feb 21 2011 Mathematics Subject Classification 05A19 06A07 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. Keywords 2 2 -free poset interval orders composition matrix dual poset bijection All authors were supported by grant no. 090038012 from the Icelandic Research Fund. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P44 1 Figure 1 Overview of known correspondences. 1 Introduction The recent introduction of bivincular patterns has unearthed surprising new connections between several combinatorial objects. Relaxing some parts of the definitions of these objects led to yet more new connections between supersets of these structures. Figure 1 summarizes the correspondences between three of these objects at three different levels . Black lines indicate that a bijection has been proven and the label on a line indicates the paper in which
