DMTCS Proceedings, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

Font Size:  Small  Medium  Large

Dyck tilings, linear extensions, descents, and inversions

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

Abstract


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.
Résumé. Les pavages de Dyck ont été introduits par Kenyon et Wilson dans leur étude du modèle des ``double-dimères''. Ce sont des pavages des diagrammes de Young gauches avec des tuiles en forme de rubans qui ressemblent à des chemins de Dyck. Nous donnons deux bijections entre les pavages de Dyck ``couvre-inclusive'' et les extensions linéaires de posets dont le diagramme de Hasse est un arbre. La première bijection transforme la statistique (aire + tuiles) / 2 en inversions de l'extension linéaire, et la deuxième bijection transforme la ``discordance'' entre la limite supériere et inférieure du pavage en descentes de l'extension linéaire.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional