Document Open Access Logo

The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem

Authors Ilse Fischer , Matjaž Konvalinka

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.12.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Author Details

Ilse Fischer
  • Faculty of Mathematics, University of Vienna, Austria
Matjaž Konvalinka
  • Faculty of Mathematics and Physics, University of Ljubljana, Slovenia
  • Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Funding

  • Fischer, Ilse: Austrian Science Foundation FWF, SFB grant F50.
  • Konvalinka, Matjaž: Slovenian Research Agency (research core funding No. P1-0294).

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.AofA.2020.12

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Enumeration
Keywords
  • enumeration
  • bijective proof
  • alternating sign matrix
  • plane partition

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. G. Andrews. Plane partitions. III. The weak Macdonald conjecture. Invent. Math., 53(3):193-225, 1979. URL: https://doi.org/10.1007/BF01389763.
  2. G. Andrews. Plane partitions. V. The TSSCPP conjecture. J. Combin. Theory Ser. A, 66(1):28-39, 1994. URL: https://doi.org/10.1016/0097-3165(94)90048-5.
  3. A. Ayyer, R. Behrend, and I. Fischer. Extreme diagonally and antidiagonally symmetric alternating sign matrices of odd order, 2016. preprint. Google Scholar
  4. A. Bauer. What is an explicit bijection? FPSAC 2019 invited lecture, available at URL: http://videolectures.net/FPSAC2019_bauer_explicit_bijection/.
  5. R. Behrend, P. Di Francesco, and P. Zinn-Justin. A doubly-refined enumeration of alternating sign matrices and descending plane partitions. J. Combin. Theory Ser. A, 120(2):409-432, 2013. URL: https://doi.org/10.1016/j.jcta.2012.09.004.
  6. R. Behrend, I. Fischer, and M. Konvalinka. Diagonally and antidiagonally symmetric alternating sign matrices of odd order. Adv. Math., 315:324-365, 2017. URL: https://doi.org/10.1016/j.aim.2017.05.014.
  7. P. Biane and H. Cheballah. Gog and GOGAm pentagons. J. Combin. Theory Ser. A, 138:133-154, 2016. URL: https://doi.org/10.1016/j.jcta.2015.10.001.
  8. D. Bressoud. Proofs and confirmations. The story of the alternating sign matrix conjecture. MAA Spectrum. Mathematical Association of America and Cambridge University Press, Washington, DC and Cambridge, 1999. Google Scholar
  9. D. Bressoud and J. Propp. How the alternating sign matrix conjecture was solved. Notices Amer. Math. Soc., 46(6):637-646, 1999. Google Scholar
  10. I. Fischer. A method for proving polynomial enumeration formulas. J. Combin. Theory Ser. A, 111:37-58, 2005. Google Scholar
  11. I. Fischer. The number of monotone triangles with prescribed bottom row. Adv. in Appl. Math., 37(2):249-267, 2006. URL: https://doi.org/10.1016/j.aam.2005.03.009.
  12. I. Fischer. A new proof of the refined alternating sign matrix theorem. J. Combin. Theory Ser. A, 114(2):253-264, 2007. URL: https://doi.org/10.1016/j.jcta.2006.04.004.
  13. I. Fischer. Short proof of the ASM theorem avoiding the six-vertex model. J. Combin. Theory Ser. A, 144:139-156, 2016. Google Scholar
  14. I. Fischer and M. Konvalinka. A bijective proof of the ASM theorem, part I: the operator formula. preprint (2019). URL: http://arxiv.org/abs/1910.04198.
  15. I. Fischer and M. Konvalinka. A bijective proof of the ASM theorem, part II: ASM enumeration and ASM-DPP relation. preprint (2019). Google Scholar
  16. T. Fonseca and P. Zinn-Justin. On the doubly refined enumeration of alternating sign matrices and totally symmetric self-complementary plane partitions. Electron. J. Combin., 15:Research Paper 81, 35 pp. (electronic), 2008. Google Scholar
  17. C. Krattenthaler. A gog-magog conjecture, 1996. URL: http://www.mat.univie.ac.at/~kratt/artikel/magog.html.
  18. C. Krattenthaler. Plane partitions in the work of Richard Stanley and his school. In The mathematical legacy of Richard P. Stanley, pages 231-261. Amer. Math. Soc., Providence, RI, 2016. Google Scholar
  19. G. Kuperberg. Another proof of the alternating-sign matrix conjecture. Internat. Math. Res. Notices, 1996(3):139-150, 1996. URL: https://doi.org/10.1155/S1073792896000128.
  20. W. Mills, D. Robbins, and H. Rumsey, Jr. Alternating sign matrices and descending plane partitions. J. Combin. Theory Ser. A, 34(3):340-359, 1983. URL: https://doi.org/10.1016/0097-3165(83)90068-7.
  21. W. Mills, D. Robbins, and H. Rumsey, Jr. Self-complementary totally symmetric plane partitions. J. Combin. Theory Ser. A, 42(2):277-292, 1986. URL: https://doi.org/10.1016/0097-3165(86)90098-1.
  22. D. Robbins and H. Rumsey. Determinants and alternating sign matrices. Adv. in Math., 62(2):169-184, 1986. URL: https://doi.org/10.1016/0001-8708(86)90099-X.
  23. V. Voevodsky. C-systems defined by universe categories: presheaves. arXiv = 1706.03620. Google Scholar
  24. D. Zeilberger. Proof of the alternating sign matrix conjecture. Electron. J. Combin., 3(2):Research Paper 13, 84 pp. (electronic), 1996. The Foata Festschrift. URL: http://www.combinatorics.org/Volume_3/Abstracts/v3i2r13.html.
  25. D. Zeilberger. Proof of the refined alternating sign matrix conjecture. New York J. Math., 2:59-68 (electronic), 1996. URL: http://nyjm.albany.edu:8000/j/1996/2_59.html.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact