Ilse Fischer ; Lukas Riegler - Combinatorial Reciprocity for Monotone Triangles

dmtcs:3042 - 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.3042
Combinatorial Reciprocity for Monotone Triangles

Authors: Ilse Fischer ORCID-iD1; Lukas Riegler 2

  • 1 Faculty of Mathematics [Vienna]
  • 2 Fakultät für Mathematik [Wien]

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.


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: Combinatorial Reciprocity, Monotone Triangle, Decreasing Monotone Triangle, Alternating Sign Matrix,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Compact enumeration formulas for generalized partitions; Funder: Austrian Science Fund (FWF); Code: Y 463

Consultation statistics

This page has been seen 169 times.
This article's PDF has been downloaded 181 times.