Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Dyck tilings, linear ...
Conference paper

Dyck tilings, linear extensions, descents, and inversions

Jang Soo Kim (1), Karola Mészáros (2), Greta Panova (3), David B. Wilson (4)
(1) University of Minnesota [Twin Cities]
(2) Department of Mathematics [Ann Arbor]
(3) University of California [Los Angeles]
(4) Microsoft Research [Redmond]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2011
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Proceedings
DOI
10.46298/dmtcs.3081
License
https://about.hal.science/hal-authorisation-v1
98052
Indicators
698
Views
637
Downloads

Dyck tilings, linear extensions, descents, and inversions

Jang Soo Kim (1), Karola Mészáros (2), Greta Panova (3), David B. Wilson (4)
(1) University of Minnesota [Twin Cities]
(2) Department of Mathematics [Ann Arbor]
(3) University of California [Los Angeles]
(4) Microsoft Research [Redmond]
Abstract
English
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.
French
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Dyck tiling
  • Dyck path
  • linear extension
  • tree poset
  • perfect matching
Preview
Loading PDF preview...