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...

Full description

Bibliographic Details
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:
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
id ftccsdartic:oai:HAL:hal-01215066v1
record_format openpolar
spelling ftccsdartic:oai:HAL:hal-01215066v1 2023-05-15T16:51:39+02:00 Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs Rubey, Martin 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 Reykjavik, Iceland 2011 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 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2957 hal-01215066 https://hal.inria.fr/hal-01215066 https://hal.inria.fr/hal-01215066/document https://hal.inria.fr/hal-01215066/file/dmAO0173.pdf doi:10.46298/dmtcs.2957 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-01215066 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.835-848, ⟨10.46298/dmtcs.2957⟩ 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] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic https://doi.org/10.46298/dmtcs.2957 2023-03-05T11:38:04Z 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. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) Greene ENVELOPE(168.233,168.233,-72.100,-72.100) Discrete Mathematics & Theoretical Computer Science DMTCS Proceeding Proceedings
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 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]
spellingShingle 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]
Rubey, Martin
Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
topic_facet 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]
description 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.
author2 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
author Rubey, Martin
author_facet Rubey, Martin
author_sort Rubey, Martin
title Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
title_short Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
title_full Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
title_fullStr Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
title_full_unstemmed Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
title_sort maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
publisher HAL CCSD
publishDate 2011
url 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
op_coverage Reykjavik, Iceland
long_lat ENVELOPE(168.233,168.233,-72.100,-72.100)
geographic Greene
geographic_facet Greene
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-01215066
23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.835-848, ⟨10.46298/dmtcs.2957⟩
op_relation info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2957
hal-01215066
https://hal.inria.fr/hal-01215066
https://hal.inria.fr/hal-01215066/document
https://hal.inria.fr/hal-01215066/file/dmAO0173.pdf
doi:10.46298/dmtcs.2957
op_rights info:eu-repo/semantics/OpenAccess
op_doi https://doi.org/10.46298/dmtcs.2957
container_title Discrete Mathematics & Theoretical Computer Science
container_volume DMTCS Proceeding
container_issue Proceedings
_version_ 1766041774607826944