Counting self-dual interval orders
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 s...
Main Author: | |
---|---|
Other Authors: | , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215055 https://hal.inria.fr/hal-01215055/document https://hal.inria.fr/hal-01215055/file/dmAO0148.pdf |
id |
ftccsdartic:oai:HAL:hal-01215055v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215055v1 2023-05-15T16:50:45+02:00 Counting self-dual interval orders Jelínek, Vít Fakultät für Mathematik Wien Universität Wien Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215055 https://hal.inria.fr/hal-01215055/document https://hal.inria.fr/hal-01215055/file/dmAO0148.pdf en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS hal-01215055 https://hal.inria.fr/hal-01215055 https://hal.inria.fr/hal-01215055/document https://hal.inria.fr/hal-01215055/file/dmAO0148.pdf info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215055 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.539-550 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] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic 2020-12-25T18:15:03Z 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. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
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] |
spellingShingle |
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] Jelínek, Vít Counting self-dual interval orders |
topic_facet |
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] |
description |
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. |
author2 |
Fakultät für Mathematik Wien Universität Wien Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel |
format |
Conference Object |
author |
Jelínek, Vít |
author_facet |
Jelínek, Vít |
author_sort |
Jelínek, Vít |
title |
Counting self-dual interval orders |
title_short |
Counting self-dual interval orders |
title_full |
Counting self-dual interval orders |
title_fullStr |
Counting self-dual interval orders |
title_full_unstemmed |
Counting self-dual interval orders |
title_sort |
counting self-dual interval orders |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01215055 https://hal.inria.fr/hal-01215055/document https://hal.inria.fr/hal-01215055/file/dmAO0148.pdf |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215055 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.539-550 |
op_relation |
hal-01215055 https://hal.inria.fr/hal-01215055 https://hal.inria.fr/hal-01215055/document https://hal.inria.fr/hal-01215055/file/dmAO0148.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766040873408135168 |