×

zbMATH — the first resource for mathematics

Associahedra via spines. (English) Zbl 1413.52017
The \(n\)-dimensional associahedron is a certain convex \(n\)-polytope whose vertices are in one-to-one correspondence with the triangulations of a convex \((n+3)\)-gon and whose edges represent pairs of triangulations related by a flip of a single diagonal. Various polytopal realizations of the associahedron are known. The present paper introduces the spine of a triangulation of the \((n+3)\)-gon as the dual graph of the triangulation together with a labeling and an orientation. The approach to associahedra via spines extends the classical description of associahedra in terms of binary trees [J.-L. Loday, Arch. Math. 83, No. 3, 267–278 (2004; Zbl 1059.52017)] and provides a new perspective on the realizations discovered in [C. Hohlweg and C. E. M. C. Lange, Discrete Comput. Geom. 37, No. 4, 517–543 (2007; Zbl 1125.52011)], leading in particular to new insights about their geometric and combinatorial properties.

MSC:
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B11 \(n\)-dimensional polytopes
20F55 Reflection and Coxeter groups (group-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] F. Ardila, C. Benedetti and J. Doker: Matroid polytopes and their volumes · Zbl 1204.52016 · doi:10.1007/s00454-009-9232-9
[2] L. J. Billera, P. Filliman and B. Sturmfels: Constructions and complexity of seconda · Zbl 0714.52004 · doi:10.1016/0001-8708(90)90077-Z
[3] A. Björner and M. Wachs: Shellable nonpure complexes and posets. II, · Zbl 0886.05126 · doi:10.1090/S0002-9947-97-01838-2
[4] M. P. Carr and S. L. Devadoss: Coxeter complexes and graph-asso · Zbl 1099.52001 · doi:10.1016/j.topol.2005.08.010
[5] C. Ceballos, J.-Ph. Labbé and C. Stump: Subword complexes, cluster complexes, and generalized multi-associahedra, J. Algebraic Combin., 2013.
[6] C. Ceballos, F. Santos and G. M. Ziegler: Many non-equivalent realizations of the asso · Zbl 1389.52013 · doi:10.1007/s00493-014-2959-9
[7] F. Chapoton, S. Fomin and A. Zelevinsky: Polytopal realizations of generalized associah · Zbl 1018.52007 · doi:10.4153/CMB-2002-054-1
[8] G. Chatel and V. Pilaud: Cambrian H · Zbl 1369.05211 · doi:10.1016/j.aim.2017.02.027
[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to algorithms, MIT Press, Cambridge, MA, third edition, 2009. · Zbl 1187.68679
[10] S. L. Devadoss: A realization of graph asso · Zbl 1189.05176 · doi:10.1016/j.disc.2007.12.092
[11] S. Fomin and A. Zelevinsky: Cluster algebras I. Foundati · Zbl 1021.16017 · doi:10.1090/S0894-0347-01-00385-X
[12] S. Fomin and A. Zelevinsky: Cluster algebras II. Finite type class · Zbl 1054.17024 · doi:10.1007/s00222-003-0302-y
[13] Á. Galambos and V. Reiner: Acyclic sets of linear orders via the Bruhat ord · Zbl 1134.91014 · doi:10.1007/s00355-007-0228-1
[14] I. Gelfand, M. Kapranov and A. Zelevinsky: Discriminants, resultants and multidimensional determinants, Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, 2008, Reprint of the 1994 edition. · Zbl 1138.14001
[15] C. Hohlweg: Permutahedra and associahedra, Pages 129-159 in [49].
[16] C. Hohlweg and C. Lange: Realizations of the associahedron and cyclohedron · Zbl 1125.52011 · doi:10.1007/s00454-007-1319-6
[17] C. Hohlweg, C. Lange and H. Thomas: Permutahedra and generalized · Zbl 1233.20035 · doi:10.1016/j.aim.2010.07.005
[18] C. Hohlweg, J. Lortie and A. Raymond: The centers of gravity of the associahedron and of the permutahedron are the same, Electron. J. C · Zbl 1225.05246
[19] K. Igusa and J. Ostroff: Mixed cobinary trees, preprint, arXiv:1307.3587, 2013. · Zbl 1395.05189
[20] A. Knutson and E. Miller: Subword complexes in Co · Zbl 1069.20026 · doi:10.1016/S0001-8708(03)00142-7
[21] J.-Ph. Labbé and C. Lange: Cambrian acyclic domains: counting c-singletons, in preparation, 2017.
[22] C. Lange: Minkowski decomposition of associahedra and related combinatorics · Zbl 1283.52014 · doi:10.1007/s00454-013-9546-5
[23] C. W. Lee: The associahedron and triangulations of the n- · Zbl 0682.52004 · doi:10.1016/S0195-6698(89)80072-1
[24] J.-L. Loday: Realization of the Stasheff polyt · Zbl 1059.52017 · doi:10.1007/s00013-004-1026-y
[25] J.-L. Loday and M. O. Ronco: Hopf algebra of the planar · Zbl 0926.16032 · doi:10.1006/aima.1998.1759
[26] C. Malvenuto and C. Reutenauer: Duality between quasi-symmetric functions and the Solomon des · Zbl 0838.05100 · doi:10.1006/jabr.1995.1336
[27] T. V. Narayana: Lattice path combinatorics with statistical applications, volume 23 of Mathematical Expositions, University of Toronto Press, Toronto, Ont., 1979. · Zbl 0437.05001
[28] V. Pilaud: Signed tree associahedra, Extended abstract in 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), preprint, arXiv:1309.5222, 2013. · Zbl 1394.52012
[29] V. Pilaud: Which nestohedra are removahe · Zbl 1384.52005 · doi:10.15446/recolma.v51n1.66833
[30] V. Pilaud and M. Pocchiola: Multitriangulations, pseudotriangulations and primitive sorting networks · Zbl 1247.52012 · doi:10.1007/s00454-012-9408-6
[31] V. Pilaud and F. Santos: The brick polytope of a sorting netw · Zbl 1239.52026 · doi:10.1016/j.ejc.2011.12.003
[32] V. Pilaud and C. Stump: EL-labelings and canonical spanning trees for subword complexes, in: Discrete Geometry and Optimization, Fields Institute Communications Series, 213–248. Springer, 2013. · Zbl 1271.05025
[33] V. Pilaud and C. Stump: Brick polytopes of spherical subword complexes and generalized · Zbl 1405.05196 · doi:10.1016/j.aim.2015.02.012
[34] V. Pilaud and C. Stump: Vertex barycenter of generalized associahedra · Zbl 1316.52022 · doi:10.1090/S0002-9939-2015-12357-X
[35] A. Postnikov: Permutohedra, associahedra, and beyond, I · Zbl 1162.52007 · doi:10.1093/imrn/rnn153
[36] A. Postnikov, V. Reiner and L. K. Williams: Faces of generalized · Zbl 1167.05005
[37] L. Pournin: The diameter of · Zbl 1292.52011 · doi:10.1016/j.aim.2014.02.035
[38] N. Reading: Lattice congruences · Zbl 1097.20036 · doi:10.1007/s11083-005-4803-8
[39] N. Reading: Cambr · Zbl 1106.20033 · doi:10.1016/j.aim.2005.07.010
[40] N. Reading and D. E. Speyer: Cambrian fans, J · Zbl 1213.20038 · doi:10.4171/JEMS/155
[41] S. Shnider and S. Sternberg: Quantum groups: From coalgebras to Drinfeld algebras, Series in Mathematical Physics. International Press, Cambridge, MA, 1993. · Zbl 0845.17015
[42] D. D. Sleator, R. E. Tarjan and W. P. Thurston: Rotation distance, triangulations, and hyperbolic sp · Zbl 0653.51017 · doi:10.1090/S0894-0347-1988-0928904-4
[43] L. Solomon: A Mackey formula in the group ring of a C · Zbl 0355.20007 · doi:10.1016/0021-8693(76)90182-4
[44] R. P. Stanley: Hipparchus, Plutarch, Schröder, and Ho
[45] R. P. Stanley: Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999.
[46] J. Stasheff: Homotopy associativity of H-spaces I, II, · Zbl 0114.39402
[47] J. Stasheff: From operads to sically” inspired theories, in: Operads: Proceedings of Renaissance Conferences (Hartfort, CT/Luminy, 1995), volume 202 of Contemporary Mathematics, 53–81, Cambridge, MA, 1997. American Mathematical Society, Appendix B by Steve Shnider and Jim Stasheff for a corrected polytope construction.
[48] S. Stella: Polyhedral models for generalized associahedra via Coxeter elemen · Zbl 1268.05242 · doi:10.1007/s10801-012-0396-7
[49] Associahedra, Tamari Lattices and Related Structures, Tamari Memorial Festschrift, F. Müller-Hoissen, J. M. Pallo and J. Stasheff eds., volume 299 of Progress in Mathematics, Springer, New York, 2012.
[50] X. Viennot: Catalan tableaux and the asymmetric exclusion process, in: 19th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2007). 2007.
[51] A. Zelevinsky: Nested complexes and their polyhedral realizati · Zbl 1109.52010 · doi:10.4310/PAMQ.2006.v2.n3.a3
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.