1 Search Results for "Fischer, Ilse"


Document
The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem

Authors: Ilse Fischer and Matjaž Konvalinka

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


Abstract
Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, but a bijective proof for any of these equivalences has been elusive for almost 40 years. In this extended abstract, we provide a sketch of the first bijective proof of the enumeration formula for alternating sign matrices, and of the fact that alternating sign matrices are equinumerous with descending plane partitions. The bijections are based on the operator formula for the number of monotone triangles due to the first author. The starting point for these constructions were known "computational" proofs, but the combinatorial point of view led to several drastic modifications and simplifications. We also provide computer code where all of our constructions have been implemented.

Cite as

Ilse Fischer and Matjaž Konvalinka. The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.AofA.2020.12,
  author =	{Fischer, Ilse and Konvalinka, Matja\v{z}},
  title =	{{The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.12},
  URN =		{urn:nbn:de:0030-drops-120424},
  doi =		{10.4230/LIPIcs.AofA.2020.12},
  annote =	{Keywords: enumeration, bijective proof, alternating sign matrix, plane partition}
}
  • Refine by Author
  • 1 Fischer, Ilse
  • 1 Konvalinka, Matjaž

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Enumeration

  • Refine by Keyword
  • 1 alternating sign matrix
  • 1 bijective proof
  • 1 enumeration
  • 1 plane partition

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail