×

The multidimensional cube recurrence. (English) Zbl 1227.05041

Summary: We introduce a recurrence which we term the multidimensional cube recurrence, generalizing the octahedron recurrence studied by Propp, Fomin and Zelevinsky [{|it S. Fomin} and A. Zelevinsky, “The Laurent phenomenon,” Adv. Appl. Math. 28, No.2, 199–144 (2002; Zbl 1012.05012)], Speyer [D.E. Speyer, “Perfect matchings and the octahedron recurrence,” J. Algebr. Comb. 25, No.3, 309–348 (2007; Zbl 1119.05092)], and Fock and Goncharov [V. Fock and A. Goncharov, “Moduli spaces of local systems and higher Teichmüller theory,” Publ. Math., Inst. Hautes Étud. Sci. 103, 1–211 (2006; Zbl 1099.14025)] and the three-dimensional cube recurrence studied by Fomin and Zelevinsky, and Carroll and Speyer [G.D. Carroll and D. Speyer, “The cube recurrence,” Electron. J. Comb. 11, No.1, Research paper R73, 31 p., electronic only (2004; Zbl 1060.05004)]. The states of this recurrence are indexed by tilings of a polygon with rhombi, and the variables in the recurrence are indexed by vertices of these tilings. We travel from one state of the recurrence to another by performing elementary flips.
We show that the values of the recurrence are independent of the order in which we perform the flips; this proof involves nontrivial combinatorial results about rhombus tilings which may be of independent interest. We then show that the multidimensional cube recurrence exhibits the Laurent phenomenon - any variable is given by a Laurent polynomial in the other variables. We recognize a special case of the multidimensional cube recurrence as giving explicit equations for the isotropic Grassmannians \(IG(n - 1,2n)\). Finally, we describe a tropical version of the multidimensional cube recurrence and show that, like the tropical octahedron recurrence, it propagates certain linear inequalities.

MSC:

05A15 Exact enumeration problems, generating functions
05B45 Combinatorial aspects of tessellation and tiling problems
52C45 Combinatorial complexity of geometric structures
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Carroll, G.; Speyer, D., The cube recurrence, Electron. J. Combin., 11 (2004), #R73 · Zbl 1060.05004
[2] Elnitsky, S., Rhombic tilings of polygons and classes of reduced words in Coxeter groups, J. Combin. Theory Ser. A, 77, 193-221 (1997) · Zbl 0867.05019
[3] Fock, V.; Goncharov, A., Moduli space of local systems and higher Teichmüller theory, Publ. Math. Inst. Hautes Études Sci., 103, 1 (2006) · Zbl 1099.14025
[4] Fomin, S.; Zelevinsky, A., The Laurent phenomenon, Adv. in Appl. Math., 28, 2, 119-144 (2002) · Zbl 1012.05012
[5] Henriques, A.; Kamnitzer, J., The octahedron recurrence and \(gl_n\)-crystals, Adv. Math., 206, 1, 211-249 (2006) · Zbl 1155.05063
[6] Kenyon, R., Tiling a polygon with parallelograms, Algorithmica, 9, 382-397 (1993) · Zbl 0778.52012
[7] Knutson, A.; Tao, T.; Woodward, C., A positive proof of the Littlewood-Richardson rule using the octahedron recurrence, Electron. J. Combin., 11 (2004), #R61 · Zbl 1053.05119
[8] Folkman, J.; Lawrence, J., Oriented matroids, J. Combin. Theory Ser. B, 25, 2, 199-236 (1978) · Zbl 0325.05019
[9] Richter-Gebert, J.; Ziegler, G., Zonotopal Tilings and the Bohne-Dress Theorem, (Contemp. Math., vol. 178 (1994), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 212-232 · Zbl 0842.05018
[10] Ringel, G., Teilungen der Ebene durch Geraden oder topologische Geraden, Math. Z., 64, 79-102 (1956) · Zbl 0070.16108
[11] Shapiro, B.; Shapiro, M.; Vainshtein, A., Connected components in the intersection of two open opposite Schubert cells in \(SL_n / B\), Int. Math. Res. Not., 10, 469-493 (1997) · Zbl 0902.14035
[12] Speyer, D., Perfect matchings and the octahedron recurrence, J. Algebraic Combin., 25, 3, 309-348 (2007) · Zbl 1119.05092
[13] Sturmfels, B.; Ziegler, G., Extension spaces of oriented matroids, Discrete Comput. Geom., 10, 23-45 (1993) · Zbl 0783.52009
[14] Ziegler, G., Higher bruhat orders and cyclic hyperplane arrangements, Topology, 32, 2, 259-279 (1993) · Zbl 0782.06003
[15] Ziegler, G., Lectures on Polytopes, Grad. Texts in Math., vol. 152 (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0823.52002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.