nLab octahedron recurrence

Idea

$$f (n, i, j) f (n-2, i, j) = f (n-1, i-1, j) f (n-1, i + 1, j) + \lambda f (n-1, i, j-1) f (n-1, i, j + 1)$$

This is a recurrence obtained in Robbins, Rumsey 1986 by extension of Desnanot-Jacobi (Lewis-Caroll) identity underlying the recursive computation of determinants called Dodgson condensation method which is obtained by setting $\lambda = 1$, $f(-1,i,j)=1$ and allowing only $n+i+j = 0\,\,\,(mod\,\,2)$.

Properties

Solutions are Laurent polynomials in $f(0,i,j)$ and $\lambda$. This is an example in cluster algebra theory.

According to Robbins, Rumsey 1986, exponents of the $f(0,i,j)$ in any monomial occurring in a $f(n_0,i_0,j_0)$ form pairs of compatible alternating sign matrices.

Birational Robinson–Schensted–Knuth correspondence satisfies the octahedron recurrence.

Literature

Appearance in the study of alternating-sign matrices

• D. P. Robbins, H. Rumsey, Determinants and alternating-sign matrices, Advances in Math. 62 (1986) 169–184 doi
• J. Propp, The many faces of alternating-sign matrices, in Discrete Models: Combinatorics, Computation, and Geometry, Discrete Math. Theor. Comput. Sci. Proc., AA, Maison Inform. Math. Discrét. (Paris, 2001) 43–58

Providing a major example in cluster algebras

• Sergey Fomin, Andrei Zelevinsky, The Laurent phenomenon, Adv. in Appl. Math. 28 (2002), no. 2, 119–144
• David E. Speyer, Perfect matchings and the octahedron recurrence, J. Algebr. Comb. (2007) 25:309–348 doi arXiv:math.CO/0402452
• V. Danilov, Gleb Koshevoy, Arrays and the octahedron recurrence, arXiv:math.CO/0504299
• André Henriques, A periodicity theorem for the octahedron recurrence, J. Algebraic Comb. 26(1), 1–26 (2007) arXiv:math.CO/0604289

Relation to crystal bases

• André Henriques, Joel Kamnitzer, The octahedron recurrence and $gl_n$ crystals, Adv. Math. 206:1 (2006) 211–249 doi

Application to Littlewood-Richardson rule

• Allen Knutson, Terence Tao, Christopher T. Woodward. A positive proof of the Littlewood-Richardson rule using the octahedron recurrence, arXiv:math.CO/0306274

Robinson–Schensted–Knuth correspondence satisfies octahedron recurrence

• V.I. Danilov, G. A. Koshevoy, The octahedron recurrence and RSK-correspondence, Sém. Lothar. Combin., 54A (2005/07) Art. B54An, 16 pp. (electronic) published pdf arXiv:math.CO/0703414

On a bijective proof of that fact

• Miriam Farber, Sam Hopkins, Wuttisak Trongsiriwat, Interlacing networks: Birational RSK, the octahedron recurrence, and Schur function identities, Journal of Combinatorial Theory A 133 (2015) 339–371 doi

category: combinatorics