DMTCS Proceedings, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)

Font Size:  Small  Medium  Large

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

Martin Rubey

Abstract


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.
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 rc-graphes, également connus sous le nom de 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 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 rc-graphes est en fait un treillis.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional