Jang Soo Kim ; Karola Mészáros ; Greta Panova ; David B. Wilson - 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) - https://doi.org/10.46298/dmtcs.3081
Dyck tilings, linear extensions, descents, and inversionsConference paper

Authors: Jang Soo Kim 1; Karola Mészáros 2; Greta Panova 3; David B. Wilson 4

[en]
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.

[fr]
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érieure et inférieure du pavage en descentes de l'extension linéaire.


Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] Dyck tiling, Dyck path, linear extension, tree poset, perfect matching
Funding:
    Source : OpenAIRE Graph
  • Bio-based solvent identification and evaluation for use in polyurethane resin binders for the roofing industry; Code: 98052

Consultation statistics

This page has been seen 416 times.
This article's PDF has been downloaded 467 times.