Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs

Résumé : Nous démontrons que les remplissages maximaux avec 0 et 1 des polyominos $L$-convexes, avec longueurs de chaînes restreintes, peuvent être identifiés avec certains $\textit{rc-graphes}$, également connus sous le nom de $\textit{pipe dreams}$. En particulier, ceci montre un lien entre ces remplissages d'un diagramme de Ferrers et les polynômes de Schubert. On en déduit en outre une preuve bijective du fait que le nombre de remplissages maximaux d'un $\textit{stack polyomino}$ $S$, avec longueurs de chaînes bornées par un entier $k$, dépend seulement de $k$ et du multi-ensemble des tailles des colonnes de $S$. Notre contribution principale est un énoncé un peu plus fort, qui nous mène à conjecturer que l'ensemble ordonné (poset) des $\textit{rc-graphes}$ est en fait un treillis.
Type de document :
Communication dans un congrès
Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.835-848, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01215066
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 13 octobre 2015 - 15:06:05
Dernière modification le : mardi 7 mars 2017 - 15:15:31
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:20:35

Fichier

dmAO0173.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01215066, version 1

Collections

Citation

Martin Rubey. Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs. Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.835-848, 2011, DMTCS Proceedings. 〈hal-01215066〉

Partager

Métriques

Consultations de la notice

36

Téléchargements de fichiers

27