The first bijective proof of the Alternating Sign Matrix theorem

Ilse Fischer, Matjaz Konvalinka

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

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.
OriginalspracheEnglisch
Titel31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Redakteure*innenMichael Drmota, Clemens Heuberger
ErscheinungsortDagstuhl
Herausgeber (Verlag)Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Seiten12:1-12:12
ISBN (Print)978-3-95977-147-4
DOIs
PublikationsstatusVeröffentlicht - 2020

Publikationsreihe

ReiheLeibniz International Proceedings in Informatics (LIPIcs)
Band159

ÖFOS 2012

  • 101012 Kombinatorik

Zitationsweisen