Kim, Jang Soo and Mészáros, Karola and Panova, Greta and Wilson, David B. - Dyck tilings, linear extensions, descents, and inversions

dmtcs:3081 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Dyck tilings, linear extensions, descents, and inversions

Authors: Kim, Jang Soo and Mészáros, Karola and Panova, Greta and Wilson, David B.

Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive'' Dyck tilings and linear extensions of tree posets. The first bijection maps the statistic (area + tiles)/2 to inversions of the linear extension, and the second bijection maps the "discrepancy'' between the upper and lower boundary of the tiling to descents of the linear extension.


Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Submitted on: January 31, 2017
Keywords: Dyck path, linear extension, tree poset, perfect matching,Dyck tiling,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 65 times.
This article's PDF has been downloaded 153 times.