Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
International audience We show that maximal 0-1-fillings of moon polynomials, with restricted chain lengths, can be identified with certain rc-graphs, also known as pipe dreams. In particular, this exhibits a connection between maximal 0-1-fillings of Ferrers shapes and Schubert polynomials. Moreove...
Published in: | Discrete Mathematics & Theoretical Computer Science |
---|---|
Main Author: | |
Other Authors: | , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215066 https://hal.inria.fr/hal-01215066/document https://hal.inria.fr/hal-01215066/file/dmAO0173.pdf https://doi.org/10.46298/dmtcs.2957 |
Summary: | International audience We show that maximal 0-1-fillings of moon polynomials, with restricted chain lengths, can be identified with certain rc-graphs, also known as pipe dreams. In particular, this exhibits a connection between maximal 0-1-fillings of Ferrers shapes and Schubert polynomials. Moreover, it entails a bijective proof showing that the number of maximal fillings of a stack polyomino $S$ with no north-east chains longer than $k$ depends only on $k$ and the multiset of column heights of $S$. Our main contribution is a slightly stronger theorem, which in turn leads us to conjecture that the poset of rc-graphs with covering relation given by generalised chute moves is in fact a lattice. 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. |
---|