The University of Michigan Combinatorics Seminar
Winter 2005
March 18, 4:10-5:00, 3866 East Hall

Combinatorial models for the octahedron and cube recurrences

David Speyer

University of California at Berkeley


Consider an array of variables indexed by the entries of a three dimensional lattice obeying the relation f(n+1,i,j)*f(n-1,i,j)=f(n,i-1,j)*f(n,i+1,j)+f(n,i,j-1)*f(n,i,j+1). This is the octahedron recurrence, which emerged from the study of the Hirota equation in integrable systems and was brought to the attention of combinatorialists by Propp. The cube recurrence is a similar relation introduced by Propp and again defined on a three dimensional lattice. Each of these recurrences was motivated by the study of the Somos sequences.

If we fix a roughly two dimensional set of initial conditions, all of the other f's are rational expressions in the initial terms. Propp conjectured and Fomin and Zelevinsky proved that in each recurrence these rational expressions are actually Laurent polynomials. Propp additionally conjectured that the coefficients of these Laurent polynomials were all 1.

I will describe combinatorial proofs of these conjectures, due to myself in the octahedral case and joint work between myself and Gabriel Carroll in the cube case. In the octahedron case, the monomials turn out to be in bijection with perfect matchings of certain planar graphs, recovering results of Ciucu and others. In the cube case, the monomials are in bijection with groves, certain highly symmetric spanning forests deserving of more study.