×

zbMATH — the first resource for mathematics

Minkowski decomposition of associahedra and related combinatorics. (English) Zbl 1283.52014
Summary: Realisations of associahedra with linear non-isomorphic normal fans can be obtained by alteration of the right-hand sides of the facet-defining inequalities from a classical permutahedron. These polytopes can be expressed as Minkowski sums and differences of dilated faces of a standard simplex as described by F. Ardila et al. [Discrete Comput. Geom. 43, No. 4, 841–854 (2010; Zbl 1204.52016)]. The coefficients \(y_I\) of such a Minkowski decomposition can be computed by Möbius inversion if tight right-hand sides \(z_I\) are known not just for the facet-defining inequalities of the associahedron but also for all inequalities of the permutahedron that are redundant for the associahedron. We show for certain families of these associahedra:
(1) How to compute the tight value \(z_I\) for any inequality that is redundant for an associahedron but facet-defining for the classical permutahedron. More precisely, each value \(z_I\) is described in terms of tight values \(z_J\) of facet-defining inequalities of the corresponding associahedron determined by combinatorial properties of \(I\).
(2) The computation of the values \(y_I\) of Ardila, Benedetti & Doker can be significantly simplified and depends on at most four values \(z_{a(I)}\), \(z_{b(I)}\), \(z_{c(I)}\) and \(z_{d(I)}\).
(3) The four indices \(a(I)\), \(b(I)\), \(c(I)\) and \(d(I)\) are determined by the geometry of the normal fan of the associahedron and are described combinatorially.
(4) A combinatorial interpretation of the values \(y_I\) using a labeled \(n\)-gon. This result is inspired from similar interpretations for vertex coordinates originally described by Loday and well-known interpretations for the \(z_I\)-values of facet-defining inequalities.

MSC:
52B10 Three-dimensional polytopes
Software:
polymake
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Ardila, F., Benedetti, C., Doker, J.: Matroid polytopes and their volumes. Discret. Comput. Geom. 43, 841-854 (2010) · Zbl 1204.52016
[2] Bergeron, N., Hohlweg, C., Lange, C., Thomas, H.: Isometry classes of generalized associahedra. Semin. Lothar. Comb. 61A, 13 (2009) · Zbl 1227.05273
[3] Blind, R., Mani-Levitska, P.: On puzzles and polytope isomorphisms. Aequ. Math. 34, 287-297 (1987) · Zbl 0634.52005
[4] Bott, R., Taubes, C.: On the self-linking of knots. J. Math. Phys. 35, 5247-5287 (1994) · Zbl 0863.57004
[5] Carr, M., Devadoss, S.L.: Coxeter complexes and graph-associahedra. Topol. Appl. 153, 2155-2168 (2006) · Zbl 1099.52001
[6] Ceballos, C., Santos, F., Ziegler, G. M.: Many Non-equivalent Realizations of the Associahedron. arXiv:1109.5544, 29 pp (Preprint, 2011) · Zbl 1389.52013
[7] Chapoton, F., Fomin, S., Zelevinksy, A.: Polytopal realizations of generalized associahedra. Can. Math. Bull. 45, 537-566 (2002) · Zbl 1018.52007
[8] Fomin, S., Zelevinksy, A.: Y-systems and generalized associahedra. Ann. Math. 158, 977-1018 (2003) · Zbl 1057.52003
[9] Fomin, S., Zelevinksy, A.: Cluster algebras iv. coefficients. Compos. Math. 143, 112-164 (2007) · Zbl 1127.16023
[10] Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes—Combinatorics and Computation, pp. 43-74. Birkhäuser, Basel (2000) · Zbl 0960.68182
[11] Hohlweg, C., Lange, C.: Realizations of the associahedron and cyclohedron. Discret. Comput. Geom. 37, 517-543 (2007) · Zbl 1125.52011
[12] Hohlweg, C., Lange, C., Thomas, H.: Permutahedra and generalized associahedra. Adv. Math. 226, 608-640 (2011) · Zbl 1233.20035
[13] Kalai, G.: A simple way to tell a simple polytope from its graph. J. Comb. Theory A 49, 381-383 (1988) · Zbl 0673.05087
[14] Loday, J.-L.: Realizations of the Stasheff polytope. Arch. Math. 83, 267-278 (2004) · Zbl 1059.52017
[15] Morton, J., Pachter, L., Shiu, A., Sturmfels, B., Wienand, O.: Convex rank tests and semigraphoids. SIAM J. Discret. Math. 23, 267-278 (2009) · Zbl 1198.62038
[16] Pilaud, V., Santos, F.: The brick polytope of a sorting network. In: Proceedings of FPSAC, Reykjavik, pp. 777-788 (2011) · Zbl 1355.52009
[17] Pilaud, V., Santos, F.: The brick polytope of a sorting network. Eur. J. Comb. 33, 632-662 (2012) · Zbl 1239.52026
[18] Postnikov, A.: Permutahedra, associahedra, and beyond. Int. Math. Res. Not. 6, 1026-1106 (2009) · Zbl 1162.52007
[19] Postnikov, A., Reiner, V., Williams, L.: Faces of generalized permutahedra. Doc. Math. 13, 207-273 (2008) · Zbl 1167.05005
[20] Reading, N., Speyer, D.: Cambrian fans. J. Eur. Math. Soc. 11, 411-447 (2009) · Zbl 1213.20038
[21] Reading, N., Speyer, D.: Combinatorial Framework for Cluster Algebras. arXiv:1111.2652, 44 pp (Preprint, 2011) · Zbl 1330.05167
[22] Rote, G., Santos, F., Streinu, I.: Expansive motions and the polytope of pointed pseudo-triangulations. In: Algorithms and Combinatorics, vol. 25, pp. 699-736. Springer, Berlin (2003) · Zbl 1077.52503
[23] Schneider, R.: Convex bodies: the Brunn-Minkowski theory. In: Encyclopedia of Mathematics and Applications, vol. 44. Cambridge University Press, Cambridge (1993) · Zbl 0798.52001
[24] Shnider, S., Stasheff, J.: From operads to “physically” inspired theories. In: Operads: Proceedings of Renaissance Conferences (Hartfort, CT/Luminy, 1995), Contemporary Mathematics, vol. 202, pp. 53-81. American Mathematical Society, Cambridge, MA (1997). Appendix B by Steve Shnider and Jim Stasheff for a corrected polytope construction
[25] Shnider, S., Sternberg, S.: Quantum Groups: From Coalgebras to Drinfeld Algebras. Series in Mathematical Physics. International Press, Cambridge, MA (1993) · Zbl 0845.17015
[26] Simion, R.: A type-B associahedron. Adv. Appl. Math. 30, 2-25 (2003) · Zbl 1047.52006
[27] Stella, S.: Polyhedral models for generalized assoziahedra via Coxeter elements. J. Algebra Comb. 38, 121-158 (2013) · Zbl 1268.05242
[28] Yang, S.-W., Zelevinksy, A.: Cluster algebras of finite type via coxeter elements and principal minors. Transform Groups 13, 855-895 (2008)
[29] Ziegler, G.M.: Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152. Springer, Heidelberg (1998) · 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.