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

• Published in: Discrete Mathematics & Theoretical Computer Science
• Main Author: Rubey, Martin
• Other Authors: Institut für Algebra, Zahlentheorie und Diskrete Mathematik (Hannover), Fakultät fur Mathematik und Physik Hannover, Leibniz Universität Hannover=Leibniz University Hannover-Leibniz Universität Hannover=Leibniz University Hannover, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2011
• Subjects: multitriangulations; rc-graphs; Edelman-Greene insertion; Schubert polynomials; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Greene; Iceland
• 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

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.