Perfect matchings and the octahedron recurrence
David E. Speyer
Clay Mathematics Institute and University of Michigan 2074 East Hall, 530 Church Street Ann Arbor MI 48109-1043 USA
DOI: 10.1007/s10801-006-0039-y
Abstract
We study a recurrence defined on a three dimensional lattice and prove that its values are Laurent polynomials in the initial conditions with all coefficients equal to one. This recurrence was studied by Propp and by Fomin and Zelivinsky. Fomin and Zelivinsky were able to prove Laurentness and conjectured that the coefficients were 1. Our proof establishes a bijection between the terms of the Laurent polynomial and the perfect matchings of certain graphs, generalizing the theory of Aztec Diamonds. In particular, this shows that the coefficients of this polynomial, and polynomials obtained by specializing its variables, are positive, a conjecture of Fomin and Zelevinsky.
Pages: 309–348
Keywords: keywords aztec diamond; perfect matching; octahedron recurrence; somos sequence; somos four; somos five; cluster algebra
Full Text: PDF
References
1. A. Berenstein, S. Fomin, and A. Zelevinsky, “Cluster algebras III: Upper bounds and double Bruhat cells,” Duke Math. J. 126(1) (2005), 1-52.
2. M. Bousquet-Mélou, J. Propp, and J. West, “Matchings graphs for Gale-Robinson recurrences,” in preparation.
3. H. Cohn, N. Elkies, and J. Propp, “Local statistics for random domino tilings of the Aztec Diamond,” Duke Math. J. 85 (1996), 117-166.
4. M. Ciucu, “Perfect matchings and perfect powers,” J. Algebraic Combin. 17 (2003), 335-375.
5. C. Dodgson, “Condensation of determinants,” in Proceedings of the Royal Society of London 15 (1866), 150-155.
6. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, “Alternating sign matrices and domino tilings,” J. Algebr. Comb. 1 (1992), 111-132 and 219-234.
7. N. Elkies, 1,2,3,5,11,37,...: Non-Recursive Solution Found, posting in sci.math.research, April 26, 1995.
8. N. Elkies, Posting to “bilinear forum” on November 27, 2000, archived at http://www. jamespropp.org/somos/elliptic.
9. S. Fomin and A. Zelivinsky, “The laurent phenomena,” Adv. Appl. Math. 28, (2002) 119-144.
10. S. Fomin and A. Zelevinsky, “Cluster algebras I: Foundations,” J. Amer. Math. Soc. 15(2) (2002), 497-529.
11. V. Fock and A. Goncharov, “Moduli spaces of local systems and higher Teichmuller theory,” preprint, available at http://www.arxiv.org/math.AG/0311149.
12. D. Gale, “Mathematical entertainments,” Math. Int. 13(1) (1991), 40-42.
13. E. Kuo, “Application of graphical condensation for enumerating matchings and tilings,” Theor. Comp. Sci. 319(1) (2004), 29-57.
14. A. Knutson, T. Tao, and C. Woodward, “A positive proof of the Littlewood-Richardson rule using the octahedron recurrence,” Electr. J. Combin. 11 (2004) Research Paper 61.
15. W. Lunnon, “The number wall algorithm: An LFSR cookbook,” J. Integ. Seq. 4 (2001), Article 0.1.1.
16. J. Propp, “Generalized domino shuffling,” Theor. Comp. Sci. 303 (2003), 267-301.
17. D. Robbins and H. Rumsey, “Determinants and alternating sign matrices,” Adv. Math. 62 (1986), 169- 184.
18. E. Whittaker and G. Watson, A Course of Modern Analysis. Cambridge University Press, London, 1962.
2. M. Bousquet-Mélou, J. Propp, and J. West, “Matchings graphs for Gale-Robinson recurrences,” in preparation.
3. H. Cohn, N. Elkies, and J. Propp, “Local statistics for random domino tilings of the Aztec Diamond,” Duke Math. J. 85 (1996), 117-166.
4. M. Ciucu, “Perfect matchings and perfect powers,” J. Algebraic Combin. 17 (2003), 335-375.
5. C. Dodgson, “Condensation of determinants,” in Proceedings of the Royal Society of London 15 (1866), 150-155.
6. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, “Alternating sign matrices and domino tilings,” J. Algebr. Comb. 1 (1992), 111-132 and 219-234.
7. N. Elkies, 1,2,3,5,11,37,...: Non-Recursive Solution Found, posting in sci.math.research, April 26, 1995.
8. N. Elkies, Posting to “bilinear forum” on November 27, 2000, archived at http://www. jamespropp.org/somos/elliptic.
9. S. Fomin and A. Zelivinsky, “The laurent phenomena,” Adv. Appl. Math. 28, (2002) 119-144.
10. S. Fomin and A. Zelevinsky, “Cluster algebras I: Foundations,” J. Amer. Math. Soc. 15(2) (2002), 497-529.
11. V. Fock and A. Goncharov, “Moduli spaces of local systems and higher Teichmuller theory,” preprint, available at http://www.arxiv.org/math.AG/0311149.
12. D. Gale, “Mathematical entertainments,” Math. Int. 13(1) (1991), 40-42.
13. E. Kuo, “Application of graphical condensation for enumerating matchings and tilings,” Theor. Comp. Sci. 319(1) (2004), 29-57.
14. A. Knutson, T. Tao, and C. Woodward, “A positive proof of the Littlewood-Richardson rule using the octahedron recurrence,” Electr. J. Combin. 11 (2004) Research Paper 61.
15. W. Lunnon, “The number wall algorithm: An LFSR cookbook,” J. Integ. Seq. 4 (2001), Article 0.1.1.
16. J. Propp, “Generalized domino shuffling,” Theor. Comp. Sci. 303 (2003), 267-301.
17. D. Robbins and H. Rumsey, “Determinants and alternating sign matrices,” Adv. Math. 62 (1986), 169- 184.
18. E. Whittaker and G. Watson, A Course of Modern Analysis. Cambridge University Press, London, 1962.