Geodesic
Maximal increasing sequences in fillings of almost-moon polyominoes
Discrete mathematics & theoretical computer science, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) (2015).

Voir la notice de l'article provenant de la source Episciences

It was proved by Rubey that the number of fillings with zeros and ones of a given moon polyomino thatdo not contain a northeast chain of a fixed size depends only on the set of column lengths of the polyomino. Rubey’sproof uses an adaption of jeu de taquin and promotion for arbitrary fillings of moon polyominoes and deduces theresult for 01-fillings via a variation of the pigeonhole principle. In this paper we present the first completely bijectiveproof of this result by considering fillings of almost-moon polyominoes, which are moon polyominoes after removingone of the rows. More precisely, we construct a simple bijection which preserves the size of the largest northeast chainof the fillings when two adjacent rows of the polyomino are exchanged. This bijection also preserves the column sumof the fillings. In addition, we also present a simple bijection that preserves the size of the largest northeast chains, therow sum and the column sum if every row of the filling has at most one 1. Thereby, we not only provide a bijectiveproof of Rubey’s result but also two refinements of it. 
@article{DMTCS_2015_special_285_a21,
     author = {Poznanovi\'c, Svetlana and Yan, Catherine H.},
     title = {Maximal increasing sequences in fillings of almost-moon polyominoes},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)},
     year = {2015},
     doi = {10.46298/dmtcs.2477},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2477/}
}
TY  - JOUR
AU  - Poznanović, Svetlana
AU  - Yan, Catherine H.
TI  - Maximal increasing sequences in fillings of almost-moon polyominoes
JO  - Discrete mathematics & theoretical computer science
PY  - 2015
VL  - DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2477/
DO  - 10.46298/dmtcs.2477
LA  - en
ID  - DMTCS_2015_special_285_a21
ER  - 
%0 Journal Article
%A Poznanović, Svetlana
%A Yan, Catherine H.
%T Maximal increasing sequences in fillings of almost-moon polyominoes
%J Discrete mathematics & theoretical computer science
%D 2015
%V DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2477/
%R 10.46298/dmtcs.2477
%G en
%F DMTCS_2015_special_285_a21
Poznanović, Svetlana; Yan, Catherine H. Maximal increasing sequences in fillings of almost-moon polyominoes. Discrete mathematics & theoretical computer science, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) (2015). doi : 10.46298/dmtcs.2477. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2477/

Cité par Sources :