Perfect matchings and the octahedron recurrence.

*(English)*Zbl 1119.05092Author’s 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 Zelevinsky. Fomin and Zelevinsky 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.

Reviewer: Lutz Volkmann (Aachen)

##### MSC:

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

##### Keywords:

Aztec diamond; Perfect matching; Octahedron recurrence; Somos sequence; Cluster algebra; Laurent polynomial##### References:

[1] | Berenstein, A.; Fomin, S.; Zelevinsky, A., Cluster algebras III: Upper bounds and double Bruhat cells, Duke Math. J., 126, 1-52, (2005) · Zbl 1135.16013 |

[2] | M. Bousquet-Mélou, J. Propp, and J. West, “Matchings graphs for Gale-Robinson recurrences,” in preparation. · Zbl 1186.05010 |

[3] | Cohn, H.; Elkies, N.; Propp, J., Local statistics for random domino tilings of the Aztec Diamond, Duke Math. J., 85, 117-166, (1996) · Zbl 0866.60018 |

[4] | Ciucu, M., Perfect matchings and perfect powers, J. Algebraic Combin., 17, 335-375, (2003) · Zbl 1020.05052 |

[5] | Dodgson, C., Condensation of determinants, Proceedings of the Royal Society of London, 15, 150-155, (1866) |

[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. · Zbl 0779.05009 |

[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] | Fomin, S.; Zelivinsky, A., The laurent phenomena, Adv. Appl. Math., 28, 119-144, (2002) · Zbl 1012.05012 |

[10] | Fomin, S.; Zelevinsky, A., Cluster algebras I: Foundations, J. Amer. Math. Soc., 15, 497-529, (2002) · Zbl 1021.16017 |

[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 · Zbl 1099.14025 |

[12] | Gale, D., Mathematical entertainments, Math. Int., 13, 40-42, (1991) |

[13] | Kuo, E., Application of graphical condensation for enumerating matchings and tilings, Theor. Comp. Sci., 319, 29-57, (2004) · Zbl 1043.05099 |

[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] | Propp, J., Generalized domino shuffling, Theor. Comp. Sci., 303, 267-301, (2003) · Zbl 1052.68095 |

[17] | Robbins, D.; Rumsey, H., Determinants and alternating sign matrices, Adv. Math., 62, 169-184, (1986) · Zbl 0611.15008 |

[18] | E. Whittaker and G. Watson, A Course of Modern Analysis. Cambridge University Press, London, 1962. · Zbl 0105.26901 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.