Permutrees

Pilaud, Vincent; Pons, Viviane

Algebraic Combinatorics, Tome 1 (2018) no. 2, pp. 173-224.

We introduce permutrees, a unified model for permutations, binary trees, Cambrian trees and binary sequences. On the combinatorial side, we study the rotation lattices on permutrees and their lattice homomorphisms, unifying the weak order, Tamari, Cambrian and boolean lattices and the classical maps between them. On the geometric side, we provide both the vertex and facet descriptions of a polytope realizing the rotation lattice, specializing to the permutahedron, the associahedra, and certain graphical zonotopes. On the algebraic side, we construct a Hopf algebra on permutrees containing the known Hopf algebraic structures on permutations, binary trees, Cambrian trees, and binary sequences.

Classification : 52B12, 16T05, 16T30

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

[2] Carr, Michael P.; Devadoss, Satyan L. Coxeter complexes and graph-associahedra, Topology Appl., Volume 153 (2006) no. 12, pp. 2155-2168 | DOI | MR | Zbl

[3] Chapoton, Frédéric Algèbres de Hopf des permutahèdres, associahèdres et hypercubes, Adv. Math., Volume 150 (2000) no. 2, pp. 264-275 | DOI | MR | Zbl

[4] Chatel, Grégory; Pilaud, Vincent Cambrian Hopf Algebras, Adv. Math., Volume 311 (2017), pp. 598-633 | DOI | MR | Zbl

[5] Dermenjian, Aram; Hohlweg, Christophe; Pilaud, Vincent The facial weak order and its lattice quotients, Trans. Amer. Math. Soc., Volume 370 (2018) no. 2, pp. 1469-1507 | DOI | MR | Zbl

[6] Duchamp, G.; Hivert, F.; Thibon, J.-Y. Noncommutative symmetric functions. VI. Free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput., Volume 12 (2002) no. 5, pp. 671-717 | DOI | MR | Zbl

[7] Gelfand, Israel M.; Krob, Daniel; Lascoux, Alain; Leclerc, Bernard; Retakh, Vladimir S.; Thibon, Jean-Yves Noncommutative symmetric functions, Adv. Math., Volume 112 (1995) no. 2, pp. 218-348 | DOI | MR | Zbl

[8] Hivert, Florent; Novelli, Jean-Christophe; Thibon, Jean-Yves The algebra of binary search trees, Theoret. Comput. Sci., Volume 339 (2005) no. 1, pp. 129-165 | DOI | MR | Zbl

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

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

[11] Krob, Daniel; Latapy, Matthieu; Novelli, Jean-Christophe; Phan, Ha-Duong; Schwer, Sylviane Pseudo-Permutations I: First Combinatorial and Lattice Properties (2001) 13th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2001)

[12] Krob, Daniel; Thibon, Jean-Yves Noncommutative symmetric functions. IV. Quantum linear groups and Hecke algebras at $q=0$, J. Algebraic Combin., Volume 6 (1997) no. 4, pp. 339-376 | DOI | MR | Zbl

[13] Lange, Carsten; Pilaud, Vincent Associahedra via spines (2017) (Preprint, arXiv:1307.4391. To appear in Combinatorica) | Zbl

[14] Lascoux, Alain; Schützenberger, Marcel-Paul Treillis et bases des groupes de Coxeter, Electron. J. Combin., Volume 3 (1996) no. 2, Research paper 27, 35 pages | MR | Zbl

[15] Loday, Jean-Louis Dialgebras, Dialgebras and related operads (Lecture Notes in Math.), Volume 1763, Springer, Berlin, 2001, pp. 7-66 | DOI | MR | Zbl

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

[17] Loday, Jean-Louis; Ronco, María O. Hopf algebra of the planar binary trees, Adv. Math., Volume 139 (1998) no. 2, pp. 293-309 | DOI | MR | Zbl

[18] Malvenuto, Claudia; Reutenauer, Christophe Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, Volume 177 (1995) no. 3, pp. 967-982 | DOI | MR | Zbl

[19] Matoušek, Jiří Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, New York, 2002, xvi+481 pages | DOI | MR | Zbl

[20] Associahedra, Tamari Lattices and Related Structures. Tamari Memorial Festschrift (Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim, eds.), Progress in Mathematics, 299, Springer, New York, 2012, xx+433 pages | DOI | MR | Zbl

[21] Novelli, Jean-Christophe On the hypoplactic monoid, Discrete Math., Volume 217 (2000) no. 1-3, pp. 315-336 Formal power series and algebraic combinatorics (Vienna, 1997) | DOI | MR | Zbl

[22] Novelli, Jean-Christophe; Thibon, Jean-Yves Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, Discrete Math., Volume 310 (2010) no. 24, pp. 3584-3606 | DOI | MR | Zbl

[23] The On-Line Encyclopedia of Integer Sequences (2010) (Published electronically at http://oeis.org)

[24] Palacios, Patricia; Ronco, María O. Weak Bruhat order on the set of faces of the permutohedron and the associahedron, J. Algebra, Volume 299 (2006) no. 2, pp. 648-678 | DOI | MR | Zbl

[25] Pilaud, Vincent Signed tree associahedra (2013) (Preprint, arXiv:1309.5222) | Zbl

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

[27] Priez, Jean-Baptiste A lattice of combinatorial Hopf algebras, Application to binary trees with multiplicities (2013) Preprint arXiv:1303.5538. Extended abstract in 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC’13, Paris) | Zbl

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

[29] Reading, Nathan Lattice congruences, fans and Hopf algebras, J. Combin. Theory Ser. A, Volume 110 (2005) no. 2, pp. 237-273 | DOI | MR | Zbl

[30] Reading, Nathan Cambrian lattices, Adv. Math., Volume 205 (2006) no. 2, pp. 313-353 | DOI | MR | Zbl

[31] Reading, Nathan Noncrossing arc diagrams and canonical join representations, SIAM J. Discrete Math., Volume 29 (2015) no. 2, pp. 736-750 | DOI | MR | Zbl

[32] Reading, Nathan; Speyer, David E. Cambrian fans, J. Eur. Math. Soc., Volume 11 (2009) no. 2, pp. 407-447 | MR | Zbl

[33] Schensted, Craige Longest increasing and decreasing subsequences, Canad. J. Math., Volume 13 (1961), pp. 179-191 | DOI | MR | Zbl

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

[35] The Sage-Combinat community Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2016) (http://wiki.sagemath.org/combinat)

[36] The Sage developers Sage Mathematics Software (2016) (http://www.sagemath.org)

[37] Viennot, Xavier Catalan tableaux and the asymmetric exclusion process, 2007 19th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2007)

[38] Zelevinsky, Andrei Nested complexes and their polyhedral realizations, Pure Appl. Math. Q., Volume 2 (2006) no. 3, pp. 655-671 | DOI | MR | Zbl

[39] Ziegler, Günter M. Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer-Verlag, New York, 1995, x+370 pages | DOI | MR | Zbl