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. Proofs of two conjec ...
Conference paper

Proofs of two conjectures of Kenyon and Wilson on Dyck tilings

Jang Soo Kim (1)
(1) University of Minnesota [Twin Cities]
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.3046
License
https://about.hal.science/hal-authorisation-v1
Indicators
652
Views
698
Downloads

Proofs of two conjectures of Kenyon and Wilson on Dyck tilings

Jang Soo Kim (1)
(1) University of Minnesota [Twin Cities]
Abstract
English
Recently, Kenyon and Wilson introduced a certain matrix M in order to compute pairing probabilities of what they call the double-dimer model. They showed that the absolute value of each entry of the inverse matrix $M^-1$ is equal to the number of certain Dyck tilings of a skew shape. They conjectured two formulas on the sum of the absolute values of the entries in a row or a column of $M^-1$. In this paper we prove the two conjectures. As a consequence we obtain that the sum of the absolute values of all entries of $M^-1$ is equal to the number of complete matchings. We also find a bijection between Dyck tilings and complete matchings.
French
Récemment, Kenyon et Wilson ont introduit une certaine matrice M afin de calculer des probabilités d'appariement dans ce qu'ils appellent le modèle double-dimère. Ils ont montrè que la valeur absolue de chaque entrée de la matrice inverse $M^-1$ est égal au nombre de pavages de Dyck d'une certaine forme gauche. Ils ont conjecturè deux formules sur la somme des valeurs absolues des entrées dans une rangée ou une colonne de $M^-1$. Dans cet article, nous prouvons les deux conjectures. En conséquence on obtient que la somme des valeurs absolues de toutes les entrées de M^-1 est égale au nombre de couplages parfaits. Nous trouvons aussi une bijection entre les pavages de Dyck et les couplages parfaits.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Dyck paths
  • Dyck tilings
  • matchings
  • Hermite histories
  • orthogonal polynomials
Cited by

Source: OpenCitations

  • Dyck tilings and the homogeneous Garnir relations for graded Specht modules

    Journal of Algebraic Combinatorics

    Authors : Matthew Fayers ORCID

    Journal reference : Volume 45, 2016, pp. 1041-1082

    DOI : 10.1007/s10801-016-0734-2
  • Fully Packed Loops in a triangle: Matchings, paths and puzzles

    Journal of Combinatorial Theory Series A

    Authors : Ilse Fischer ORCID, Philippe Nadeau ORCID

    Journal reference : Volume 130, 2014, pp. 64-118

    DOI : 10.1016/j.jcta.2014.10.008
  • The Space of Circular Planar Electrical Networks

    arXiv (Cornell University)

    Authors : Richard W. Kenyon ORCID, David B. Wilson

    Journal reference : Volume 31, 2017, pp. 1-28

    DOI : 10.1137/140997798
  • Dyck tilings, increasing trees, descents, and inversions

    arXiv (Cornell University)

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

    Journal reference : Volume 122, 2013, pp. 9-27

    DOI : 10.1016/j.jcta.2013.09.008
  • Generalized Dyck tilings

    European Journal of Combinatorics

    Authors : Matthieu Josuat-Vergès ORCID, Jang Soo Kim ORCID

    Journal reference : Volume 51, 2015, pp. 458-474

    DOI : 10.1016/j.ejc.2015.07.015
  • Boundary Correlations in Planar LERW and UST

    arXiv (Cornell University)

    Authors : Alex Karrila, Kalle Kytölä, Eveliina Peltola

    Journal reference : Volume 376, 2019, pp. 2065-2145

    DOI : 10.1007/s00220-019-03615-0
  • Pfaffian Formulas for Spanning Tree Probabilities

    arXiv (Cornell University)

    Authors : GRETA PANOVA ORCID, DAVID B. WILSON

    Journal reference : Volume 26, 2016, pp. 118-137

    DOI : 10.1017/s0963548316000183
  • Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs

    Journal of the American Mathematical Society

    Authors : Richard Kenyon ORCID, David Wilson

    Journal reference : Volume 28, 2014, pp. 985-1030

    DOI : 10.1090/s0894-0347-2014-00819-5
Preview
Loading PDF preview...