Counting self-dual interval orders

• Main Author: Jelínek, Vít
• Other Authors: Fakultät für Mathematik Wien, Universität Wien, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2011
• Subjects: interval orders; (\textrm2+2)-free posets; self-dual posets; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Iceland
• Online Access: https://hal.inria.fr/hal-01215055; https://hal.inria.fr/hal-01215055/document; https://hal.inria.fr/hal-01215055/file/dmAO0148.pdf

International audience In this paper, we first derive an explicit formula for the generating function that counts unlabeled interval orders (a.k.a. (2+2)-free posets) with respect to several natural statistics, including their size, magnitude, and the number of minimal and maximal elements. In the second part of the paper, we derive a generating function for the number of self-dual unlabeled interval orders, with respect to the same statistics. Our method is based on a bijective correspondence between interval orders and upper-triangular matrices in which each row and column has a positive entry. Dans cet article, on obtient une expression explicite pour la fonction génératrice du nombre des ensembles partiellement ordonnés (posets) qui évitent le motif (2+2). La fonction compte ces ensembles par rapport à plusieurs statistiques naturelles, incluant le nombre d'éléments, le nombre de niveaux, et le nombre d'éléments minimaux et maximaux. Dans la deuxième partie, on obtient une expression similaire pour la fonction génératrice des posets autoduaux évitant le motif (2+2). On obtient ces résultats à l'aide d'une bijection entre les posets évitant (2+2) et les matrices triangulaires supérieures dont chaque ligne et chaque colonne contient un élément positif.