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. Combinatorial Recipr ...
Conference paper

Combinatorial Reciprocity for Monotone Triangles

Ilse Fischer ORCID (1) (2) (3), Lukas Riegler (4)
(1) Faculty of Mathematics [Vienna]
(2) Faculty of Mathematics [Univ. Vienna]
(3) Faculty of Mathematics = Fakultät für Mathematik [Vienne, Autriche]
(4) Fakultät für Mathematik [Wien]
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.3042
License
https://about.hal.science/hal-authorisation-v1
Y 463
Indicators
671
Views
735
Downloads

Combinatorial Reciprocity for Monotone Triangles

Ilse Fischer ORCID (1) (2) (3), Lukas Riegler (4)
(1) Faculty of Mathematics [Vienna]
(2) Faculty of Mathematics [Univ. Vienna]
(3) Faculty of Mathematics = Fakultät für Mathematik [Vienne, Autriche]
(4) Fakultät für Mathematik [Wien]
Abstract
English
The number of Monotone Triangles with bottom row $k_1 < k_2 < ⋯< k_n$ is given by a polynomial $\alpha (n; k_1,\ldots,k_n)$ in $n$ variables. The evaluation of this polynomial at weakly decreasing sequences $k_1 ≥k_2 ≥⋯≥k_n $turns out to be interpretable as signed enumeration of new combinatorial objects called Decreasing Monotone Triangles. There exist surprising connections between the two classes of objects – in particular it is shown that $\alpha (n;1,2,\ldots,n) = \alpha (2n; n,n,n-1,n-1,\ldots,1,1)$. In perfect analogy to the correspondence between Monotone Triangles and Alternating Sign Matrices, the set of Decreasing Monotone Triangles with bottom row $(n,n,n-1,n-1,\ldots,1,1)$ is in one-to-one correspondence with a certain set of ASM-like matrices, which also play an important role in proving the claimed identity algebraically. Finding a bijective proof remains an open problem.
French
Le nombre de Triangles Monotones ayant pour dernière ligne $k_1 < k_2 < ⋯< k_n$ est donné par un polynôme $\alpha (n; k_1,\ldots,k_n)$ en $n$ variables. Il se trouve que les valeurs de ce polynôme en les suites décroissantes $k_1 ≥k_2 ≥⋯≥k_n$ peuvent s'interpréter comme l'énumération signée de nouveaux objets appelés Triangles Monotones Décroissants. Il existe des liens surprenants entre ces deux classes d'objets – en particulier on prouvera l'identité $\alpha (n;1,2,\ldots,n) = \alpha (2n; n,n,n-1,n-1,\ldots,1,1)$. En parfaite analogie avec la correspondance entre Triangles Monotones et Matrices à Signe Alternant, l'ensemble des Triangles Monotones Décroissants ayant pour dernière ligne $(n,n,n-1,n-1,\ldots,1,1)$ est en correspondance biunivoque avec un certain ensemble de matrices similaires aux MSAs, ce qui joue un rôle important dans la preuve algébrique de l'identité précédente. C'est un problème ouvert que d'en donner une preuve bijective.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Combinatorial Reciprocity
  • Monotone Triangle
  • Decreasing Monotone Triangle
  • Alternating Sign Matrix
Preview
Loading PDF preview...