Perfect matchings and the octahedron recurrence

By David E. Speyer. 2004

168 citations recorded by the source corpus.

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.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/2812be432ce937c30d0628032b74eb25ee9dd043

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

The Pentagram Map: A Discrete Integrable System (2008, background): “On the other hand, it was shown in [21] that a certain change of coordinates brings the pentagram map rather closely in line with the octahedral recurrence, which is one of the prime examples in the theory of cluster algebras, see [11,18,22].”
The twist for positroid varieties (2016, background): “The proposal that matchings of a planar graph should be described by a generating functions whose variables are assigned to faces, and where the exponent of a face f should be Bf − 1 − #{e ∈ M : ∂fe = 1}, first occurred in [34].”
Discrete monodromy, pentagrams, and the method of condensation (2007, background): “See [FZ], [ Sp ], and the references therein for work in this topic.”
Introduction to Cluster Algebras. Chapters 1-3 (2016, unknown): “In particular, the numbers zm defined above can be shown to count perfect matchings in certain planar bipartite graphs, see [49] and Figure 3.”
T-systems and Y-systems in integrable systems (2010, background): “Apart from this, there are numerous aspects in type A T-system, sometimes called octahedron recurrence, related to discrete geometry [226, 227, 228], Littlewood-Richardson rule [229], perfect matchings and partition functions on a network [230, 231] and so forth.”
Dimers and cluster integrable systems (2011, unknown): “n a square grid on a torus. The transformation Ahas appeared in various guises in the literature. A version of the transformation Aﬁrst appeared in [Kor93]. It was called the octahedron recurrence in [Spey04]; the relation of the octaherdon reccurence with the Hirota bilinear diﬀerence 61 equation [”