Volume 7 (2024)
Chapoton, Frédéric;  Pilaud, Vincent
Shuffles of deformed permutahedra, multiplihedra, constrainahedra, and biassociahedra
Annales Henri Lebesgue, Volume 7 (2024), pp. 1535-1601.

Metadata

DOI10.5802/ahl.225
Keywords Deformed permutahedra, permutahedra, associahedra

Abstract

We introduce the shuffle of deformed permutahedra (a.k.a. generalized permutahedra), a simple associative operation obtained as the Cartesian product followed by the Minkowski sum with the graphical zonotope of a complete bipartite graph. Besides preserving the class of graphical zonotopes (the shuffle of two graphical zonotopes is the graphical zonotope of the join of the graphs), this operation is particularly relevant when applied to the classical permutahedra and associahedra. First, the shuffle of an m-permutahedron with an n-associahedron gives the (m,n)-multiplihedron, whose face structure is encoded by m-painted n-trees, generalizing the classical multiplihedron. We show in particular that the graph of the (m,n)-multiplihedron is the Hasse diagram of a lattice generalizing the weak order on permutations and the Tamari lattice on binary trees. Second, the shuffle of an m-associahedron with an n-associahedron gives the (m,n)-constrainahedron, whose face structure is encoded by (m,n)-cotrees, and reflects collisions of particles constrained on a grid. Third, the shuffle of an m-anti-associahedron with an n-associahedron gives the (m,n)-biassociahedron, whose face structure is encoded by (m,n)-bitrees, with relevant connections to bialgebras up to homotopy. We provide explicit vertex, facet, and Minkowski sum descriptions of these polytopes, as well as summation formulas for their f-polynomials based on generating functionology of decorated trees.


References

[AA23] Aguiar, Marcelo; Ardila, Federico Hopf monoids and generalized permutahedra, Memoirs of the American Mathematical Society, 1437, American Mathematical Society, 2023 | DOI

[ABD10] Ardila, Federico; Benedetti, Carolina; Doker, Jeffrey Matroid polytopes and their volumes, Discrete Comput. Geom., Volume 43 (2010) no. 4, pp. 841-854 | DOI | MR | Zbl

[AD13] Ardila, Federico; Doker, Jeffrey Lifted generalized permutahedra and composition polynomials, Adv. Appl. Math., Volume 50 (2013) no. 4, pp. 607-633 | DOI | MR | Zbl

[AK99a] Arakawa, Tsuneo; Kaneko, Masanobu Multiple zeta values, poly-Bernoulli numbers, and related zeta functions, Nagoya Math. J., Volume 153 (1999), pp. 189-209 | DOI | MR | Zbl

[AK99b] Arakawa, Tsuneo; Kaneko, Masanobu On poly-Bernoulli numbers, Comment. Math. Univ. St. Pauli, Volume 48 (1999) no. 2, pp. 159-167 | MR | Zbl

[BBM19] Benedetti, Carolina; Bergeron, Nantel; Machacek, John Hypergraphic polytopes: combinatorial properties and antipode, J. Comb., Volume 10 (2019) no. 3, pp. 515-544 | DOI | MR | Zbl

[BH15] Bényi, Beáta; Hajnal, Péter Combinatorics of poly-Bernoulli numbers, Stud. Sci. Math. Hung., Volume 52 (2015) no. 4, pp. 537-558 | DOI | MR | Zbl

[BH17] Bényi, Beáta; Hajnal, Péter Combinatorial properties of poly-Bernoulli relatives, Integers, Volume 17 (2017), A31 | MR | Zbl

[BM21] Barnard, Emily; McConville, Thomas Lattices from graph associahedra and subalgebras of the Malvenuto–Reutenauer algebra, Algebra Univers., Volume 82 (2021) no. 1, 2 | DOI | MR | Zbl

[Bot19] Bottman, Nathaniel 2-associahedra, Algebr. Geom. Topol., Volume 19 (2019) no. 2, pp. 743-806 | DOI | MR | Zbl

[BP22] Bottman, Nathaniel; Poliakova, Daria Constrainahedra (2022) (2208.14529)

[BW91] Björner, Anders; Wachs, Michelle L. Permutation statistics and linear extensions of posets, J. Comb. Theory, Ser. A, Volume 58 (1991) no. 1, pp. 85-114 | DOI | MR | Zbl

[CGRS14] Cameron, Peter J.; Glass, Celia A.; Rekvényi, Kamilla; Schumacher, Robert U. Acyclic orientations and poly-Bernoulli numbers (2014) | arXiv

[CZ12] Ceballos, Cesar; Ziegler, Günter M. Realizing the associahedron: mysteries and questions, Associahedra, Tamari lattices and related structures (Progress in Mathematics), Volume 299, Springer, 2012, pp. 119-127 | DOI | Zbl

[DF08] Devadoss, Satyan; Forcey, Stefan Marked tubes and the graph multiplihedron, Algebr. Geom. Topol., Volume 8 (2008) no. 4, pp. 2081-2108 | DOI | MR | Zbl

[Edm70] Edmonds, Jack Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications, Gordon and Breach Science Publishers (1970), pp. 69-87 | Zbl

[FLS10] Forcey, Stefan; Lauve, Aaron; Sottile, Frank Hopf structures on the multiplihedra, SIAM J. Discrete Math., Volume 24 (2010) no. 4, pp. 1250-1271 | DOI | MR | Zbl

[For08] Forcey, Stefan Convex hull realizations of the multiplihedra, Topology Appl., Volume 156 (2008) no. 2, pp. 326-347 | DOI | MR | Zbl

[FS05] Feichtner, Eva Maria; Sturmfels, Bernd Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), Volume 62 (2005) no. 4, pp. 437-468 | MR | Zbl

[FS09] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge University Press, 2009 | DOI | MR | Zbl

[Gre77] Greene, Curtis Acyclic orientations, Proceedings of the NATO Advanced Study Institute held in Berlin (West Germany) (Nato Science Series C), Volume 31, Springer (1977), pp. 65-68 | Zbl

[GZ83] Greene, Curtis; Zaslavsky, Thomas On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Am. Math. Soc., Volume 280 (1983) no. 1, pp. 97-126 | DOI | MR | Zbl

[HL07] Hohlweg, Christophe; Lange, Carsten Realizations of the associahedron and cyclohedron, Discrete Comput. Geom., Volume 37 (2007) no. 4, pp. 517-543 | DOI | MR | Zbl

[HLT11] Hohlweg, Christophe; Lange, Carsten; Thomas, Hugh Permutahedra and generalized associahedra, Adv. Math., Volume 226 (2011) no. 1, pp. 608-640 | DOI | MR | Zbl

[HPS18] Hohlweg, Christophe; Pilaud, Vincent; Stella, Salvatore Polytopal realizations of finite type g-vector fans, Adv. Math., Volume 328 (2018), pp. 713-749 | DOI | MR | Zbl

[Kan97] Kaneko, Masanobu Poly-Bernoulli numbers, J. Théor. Nombres Bordx, Volume 9 (1997) no. 1, pp. 221-228 | DOI | Numdam | MR | Zbl

[Kim08] Kim, Sangwook Shellable complexes and topology of diagonal arrangements, Discrete Comput. Geom., Volume 40 (2008) no. 2, pp. 190-213 | DOI | MR | Zbl

[Lan13] Lange, Carsten Minkowski Decomposition of Associahedra and Related Combinatorics, Discrete Comput. Geom., Volume 50 (2013) no. 4, pp. 903-939 | DOI | MR | Zbl

[Lod04] Loday, Jean-Louis Realization of the Stasheff polytope, Arch. Math., Volume 83 (2004) no. 3, pp. 267-278 | DOI | Zbl

[Mar15] Markl, Martin Bipermutahedron and biassociahedron, J. Homotopy Relat. Struct., Volume 10 (2015) no. 2, pp. 205-238 | DOI | MR | Zbl

[McM73] McMullen, Peter Representations of polytopes and polyhedral sets, Geom. Dedicata, Volume 2 (1973), pp. 83-99 | DOI | MR | Zbl

[Mey74] Meyer, Walter Indecomposable polytopes, Trans. Am. Math. Soc., Volume 190 (1974), pp. 77-86 | DOI | MR | Zbl

[MW10] Ma’u, Sione; Woodward, Chris Geometric realizations of the multiplihedra, Compos. Math., Volume 146 (2010) no. 4, pp. 1002-1028 | DOI | MR | Zbl

[MW18] Merkulov, Sergei; Willwacher, Thomas An explicit two step quantization of Poisson structures and Lie bialgebras, Commun. Math. Phys., Volume 364 (2018) no. 2, pp. 505-578 | DOI | MR | Zbl

[OEIS10] OEIS The On-Line Encyclopedia of Integer Sequences, 2010 (published electronically at https://oeis.org)

[Pil24] Pilaud, Vincent Acyclic reorientation lattices and their lattice quotients, Ann. Comb., Volume 28 (2024) no. 4, pp. 1035-1092 | DOI | MR | Zbl

[Pol21] Poliakova, Daria Homotopical algebra and combinatorics of polytopes, Ph. D. Thesis, University of Copenhagen, Denmark (2021)

[Pos09] Postnikov, Alexander Permutohedra, associahedra, and beyond, Int. Math. Res. Not. (2009) no. 6, pp. 1026-1106 | DOI | MR | Zbl

[PP18] Pilaud, Vincent; Pons, Viviane Permutrees, Algebr. Comb., Volume 1 (2018) no. 2, pp. 173-224 | DOI | Numdam | MR | Zbl

[PPPP23] Padrol, Arnau; Palu, Yann; Pilaud, Vincent; Plamondon, Pierre-Guy Associahedra for finite type cluster algebras and minimal relations between g-vectors, Proc. Lond. Math. Soc. (3), Volume 127 (2023) no. 3, pp. 513-588 | DOI | MR | Zbl

[PPR23] Padrol, Arnau; Pilaud, Vincent; Ritter, Julian Shard polytopes, Int. Math. Res. Not., Volume 2023 (2023) no. 9, pp. 7686-7796 | DOI | MR | Zbl

[PRW08] Postnikov, Alexander; Reiner, Victor; Williams, Lauren K. Faces of generalized permutohedra, Doc. Math., Volume 13 (2008), pp. 207-273 | DOI | MR | Zbl

[PS19] Pilaud, Vincent; Santos, Francisco Quotientopes, Bull. Lond. Math. Soc., Volume 51 (2019) no. 3, pp. 406-420 | DOI | MR | Zbl

[PSZ23] Pilaud, Vincent; Santos, Francisco; Ziegler, Günter M. Celebrating Loday’s associahedron, Arch. Math., Volume 121 (2023) no. 5-6, pp. 559-601 | DOI | Zbl

[Rea04] Reading, Nathan Lattice congruences of the weak order, Order, Volume 21 (2004) no. 4, pp. 315-344 | DOI | MR | Zbl

[SS93] Shnider, Steve; Sternberg, Shlomo Quantum groups: From coalgebras to Drinfeld algebras, Series in Mathematical Physics, International Press, 1993, 592 pages | MR | Zbl

[Sta63] Stasheff, James D. Homotopy associativity of H-spaces. I, II, Trans. Amer. Math. Soc., Volume 108 (1963), p. 275-292, 293–312 | DOI | MR | Zbl

[Sta70] Stasheff, James D. H-spaces from a homotopy point of view, Lecture Notes in Mathematics, 161, Springer, 1970 | DOI | MR | Zbl

[SU04] Saneblidze, Samson; Umble, Ronald Diagonals on the permutahedra, multiplihedra and associahedra, Homology Homotopy Appl., Volume 6 (2004) no. 1, pp. 363-411 | DOI | MR | Zbl

[SU11] Saneblidze, Samson; Umble, Ronald Matrads, biassociahedra, and A ∞ -bialgebras, Homology Homotopy Appl., Volume 13 (2011) no. 1, pp. 1-57 | DOI | MR | Zbl

[Tie16] Tierney, Patrick Realizing the 2-Associahedron, Ph. D. Thesis (2016) (HMC Senior Theses)

[Zie95] Ziegler, Günter M. Lectures on Polytopes, Graduate Texts in Mathematics, 152, Springer, 1995 | DOI | MR | Zbl