×

zbMATH — the first resource for mathematics

Compatibility fans for graphical nested complexes. (English) Zbl 1362.05140
Summary: Graph associahedra generalize classical associahedra. They realize the nested complex of a graph \(G\), i.e. the simplicial complex whose vertices are the tubes (connected induced subgraphs) of \(G\) and whose faces are the tubings (collections of pairwise nested or non-adjacent tubes) of \(G\). The constructions of M. Carr and S. L. Devadoss [Topology Appl. 153, No. 12, 2155–2168 (2006; Zbl 1099.52001)], of A. Postnikov [Int. Math. Res. Not. 2009, No. 6, 1026–1106 (2009; Zbl 1162.52007)], and of A. Zelevinsky [Pure Appl. Math. Q. 2, No. 3, 655–671 (2006; Zbl 1109.52010)] for graph associahedra are all based on the nested fan, which coarsens the normal fan of the permutahedron. In view of the variety of fan realizations of associahedra, it is tempting to look for alternative fans realizing graphical nested complexes. Motivated by the analogy between finite type cluster complexes and graphical nested complexes, we transpose S. Fomin and A. Zelevinsky’s [Invent. Math. 154, No. 1, 63–121 (2003; Zbl 1054.17024)] compatibility fans from the former to the latter setting. We define a compatibility degree between two tubes of a graph \(G\) and show that the compatibility vectors of all tubes of \(G\) with respect to an arbitrary maximal tubing on \(G\) support a fan realizing the nested complex of \(G\). When \(G\) is a path, we recover F. Santos’ Catalan many realizations of the associahedron.

MSC:
05E45 Combinatorial aspects of simplicial complexes
05B45 Combinatorial aspects of tessellation and tiling problems
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bergeron, Nantel; Hohlweg, Christophe; Lange, Carsten; Thomas, Hugh, Isometry classes of generalized associahedra, Sém. Lothar. Combin., 61A, (2009), Art. B61Aa, 13 · Zbl 1227.05273
[2] Billera, Louis J.; Filliman, Paul; Sturmfels, Bernd, Constructions and complexity of secondary polytopes, Adv. Math., 83, 2, 155-179, (1990) · Zbl 0714.52004
[3] Carr, Michael P.; Devadoss, Satyan L., Coxeter complexes and graph-associahedra, Topology Appl., 153, 12, 2155-2168, (2006) · Zbl 1099.52001
[4] Ceballos, Cesar; Pilaud, Vincent, Denominator vectors and compatibility degrees in cluster algebras of finite types, Trans. Amer. Math. Soc., 367, 1421-1439, (2015) · Zbl 1350.13020
[5] Ceballos, Cesar; Santos, Francisco; Ziegler, Günter M., Many non-equivalent realizations of the associahedron, Combinatorica, 35, 5, 513-551, (2015) · Zbl 1389.52013
[6] Chapoton, Frédéric, Algèbres de Hopf des permutahèdres, associahèdres et hypercubes, Adv. Math., 150, 2, 264-275, (2000) · Zbl 0958.16038
[7] Chapoton, Frédéric; Fomin, Sergey; Zelevinsky, Andrei, Polytopal realizations of generalized associahedra, Canad. Math. Bull., 45, 4, 537-566, (2002) · Zbl 1018.52007
[8] Chatel, Grégory; Pilaud, Vincent, Cambrian Hopf algebras, (2014), to appear in Adv. Math. · Zbl 1369.05211
[9] De Concini, Conrado; Procesi, Claudio, Wonderful models of subspace arrangements, Selecta Math. (N.S.), 1, 3, 459-494, (1995) · Zbl 0842.14038
[10] De Loera, Jesus A.; Rambau, Jörg; Santos, Francisco, Triangulations: structures for algorithms and applications, Algorithms Comput. Math., vol. 25, (2010), Springer-Verlag · Zbl 1207.52002
[11] Dehornoy, Patrick, On the rotation distance between binary trees, Adv. Math., 223, 4, 1316-1355, (2010) · Zbl 1188.05060
[12] Devadoss, Satyan L., A realization of graph associahedra, Discrete Math., 309, 1, 271-276, (2009) · Zbl 1189.05176
[13] Devadoss, Satyan L.; Forcey, Stefan; Reisdorf, Stephen; Showers, Patrick, Convex polytopes from nested posets, European J. Combin., 43, 229-248, (2015) · Zbl 1301.05231
[14] Devadoss, Satyan L.; Heath, Timothy; Vipismakul, Wasin, Deformations of bordered surfaces and convex polytopes, Notices Amer. Math. Soc., 58, 4, 530-541, (2011) · Zbl 1231.32010
[15] Feichtner, Eva Maria; Sturmfels, Bernd, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), 62, 4, 437-468, (2005) · Zbl 1092.52006
[16] Fomin, Sergey; Zelevinsky, Andrei, Cluster algebras. I. foundations, J. Amer. Math. Soc., 15, 2, 497-529, (2002), (electronic) · Zbl 1021.16017
[17] Fomin, Sergey; Zelevinsky, Andrei, Cluster algebras. II. finite type classification, Invent. Math., 154, 1, 63-121, (2003) · Zbl 1054.17024
[18] Fomin, Sergey; Zelevinsky, Andrei, Y-systems and generalized associahedra, Ann. of Math. (2), 158, 3, 977-1018, (2003) · Zbl 1057.52003
[19] Fomin, Sergey; Zelevinsky, Andrei, Cluster algebras. IV. coefficients, Compos. Math., 143, 1, 112-164, (2007) · Zbl 1127.16023
[20] Gelfand, Israel; Kapranov, Mikhail M. M.; Zelevinsky, Andrei, Discriminants, resultants and multidimensional determinants, Mod. Birkhäuser Class., (2008), Birkhäuser Boston Inc. Boston, MA, reprint of the 1994 edition · Zbl 1138.14001
[21] Hivert, Florent; Novelli, Jean-Christophe; Thibon, Jean-Yves, The algebra of binary search trees, Theoret. Comput. Sci., 339, 1, 129-165, (2005) · Zbl 1072.05052
[22] Hohlweg, Christophe, Permutahedra and associahedra, (Müller-Hoissen, Folkert; Pallo, Jean; Stasheff, Jim, Associahedra, Tamari Lattices and Related Structures - Tamari Memorial Festschrift, Progr. Math., vol. 299, (2012), Birkhäuser), 129-159 · Zbl 1271.52012
[23] Hohlweg, Christophe; Lange, Carsten, Realizations of the associahedron and cyclohedron, Discrete Comput. Geom., 37, 4, 517-543, (2007) · Zbl 1125.52011
[24] Hohlweg, Christophe; Lange, Carsten; Thomas, Hugh, Permutahedra and generalized associahedra, Adv. Math., 226, 1, 608-640, (2011) · Zbl 1233.20035
[25] Hohlweg, Christophe; Lortie, Jonathan; Raymond, Annie, The centers of gravity of the associahedron and of the permutahedron are the same, Electron. J. Combin., 17, 1, (2010), Research Paper 72, 14 · Zbl 1225.05246
[26] Hurtado, Ferran; Noy, Marc, Graph of triangulations of a convex polygon and tree of triangulations, Comput. Geom., 13, 3, 179-188, (1999) · Zbl 0948.68127
[27] Lam, Thomas; Pylyavskyy, Pavlo, Laurent phenomenon algebras, (2012), preprint · Zbl 1430.13036
[28] Lam, Thomas; Pylyavskyy, Pavlo, Linear Laurent phenomenon algebras, (2012), preprint · Zbl 1430.13036
[29] Lange, Carsten; Pilaud, Vincent, Associahedra via spines, Combinatorica, (2013), in press · Zbl 1413.52017
[30] Lee, Carl W., The associahedron and triangulations of the n-gon, European J. Combin., 10, 6, 551-560, (1989) · Zbl 0682.52004
[31] Loday, Jean-Louis, Realization of the stasheff polytope, Arch. Math. (Basel), 83, 3, 267-278, (2004) · Zbl 1059.52017
[32] Loday, Jean-Louis; Ronco, María O., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309, (1998) · Zbl 0926.16032
[33] Mark Haiman, Constructing the associahedron, Unpublished manuscript, 11 pages, available at http://www.math.berkeley.edu/ mhaiman/ftp/assoc/manuscript.pdf, 1984.
[34] (Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim, Associahedra, Tamari Lattices and Related Structures. Tamari Memorial Festschrift, Progr. Math., vol. 299, (2012), Birkhäuser Basel) · Zbl 1253.00013
[35] The on-line encyclopedia of integer sequences, (2010), Published electronically at
[36] Pilaud, Vincent, Signed tree associahedra, (2013), preprint · Zbl 1394.52012
[37] Pilaud, Vincent; Santos, Francisco, The brick polytope of a sorting network, European J. Combin., 33, 4, 632-662, (2012) · Zbl 1239.52026
[38] Pilaud, Vincent; Stump, Christian, Brick polytopes of spherical subword complexes and generalized associahedra, Adv. Math., 276, 1-61, (2015) · Zbl 1405.05196
[39] Pilaud, Vincent; Stump, Christian, Vertex barycenter of generalized associahedra, Proc. Amer. Math. Soc., 143, 6, 2623-2636, (2015) · Zbl 1316.52022
[40] Postnikov, Alexander, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN, 6, 1026-1106, (2009) · Zbl 1162.52007
[41] Pournin, Lionel, The diameter of associahedra, Adv. Math., 259, 13-42, (2014) · Zbl 1292.52011
[42] Reading, Nathan, Lattice congruences of the weak order, Order, 21, 4, 315-344, (2005), 2004 · Zbl 1097.20036
[43] Reading, Nathan, Cambrian lattices, Adv. Math., 205, 2, 313-353, (2006) · Zbl 1106.20033
[44] Reading, Nathan, Universal geometric cluster algebras, Math. Z., 277, 1-2, 499-547, (2014) · Zbl 1328.13034
[45] Reading, Nathan; Speyer, David E., Cambrian fans, J. Eur. Math. Soc. (JEMS), 11, 2, 407-447, (2009) · Zbl 1213.20038
[46] Rote, Günter; Santos, Francisco; Streinu, Ileana, Expansive motions and the polytope of pointed pseudo-triangulations, (Discrete and Computational Geometry, Algorithms Combin., vol. 25, (2003), Springer Berlin), 699-736 · Zbl 1077.52503
[47] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P., Rotation distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc., 1, 3, 647-681, (1988) · Zbl 0653.51017
[48] Stasheff, Jim, Homotopy associativity of H-spaces I, II, Trans. Amer. Math. Soc., 108, 2, 293-312, (1963) · Zbl 0114.39402
[49] Stella, Salvatore, Polyhedral models for generalized associahedra via Coxeter elements, J. Algebraic Combin., 38, 1, 121-158, (2013) · Zbl 1268.05242
[50] Tamari, Dov, Monoïdes préordonnés et chaînes de malcev, (1951), Université Paris Sorbonne, PhD thesis · Zbl 0055.01501
[51] Volodin, Vadim, Cubical realizations of flag nestohedra and a proof of Gal’s conjecture for them, Uspekhi Mat. Nauk, 65, 1(391), 183-184, (2010) · Zbl 1204.52014
[52] Zelevinsky, Andrei, Nested complexes and their polyhedral realizations, Pure Appl. Math. Q., 2, 3, 655-671, (2006) · Zbl 1109.52010
[53] Ziegler, Günter M., Lectures on polytopes, Grad. Texts in Math., vol. 152, (1995), 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. 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.