Permutrees
Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 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.
Received : 2017-08-04
Accepted : 2017-08-14
Published online : 2018-03-02
DOI : https://doi.org/10.5802/alco.1
Classification:  52B12,  16T05,  16T30
@article{ALCO_2018__1_2_173_0,
     author = {Pilaud, Vincent and Pons, Viviane},
     title = {Permutrees},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     pages = {173-224},
     doi = {10.5802/alco.1},
     zbl = {06882339},
     language = {en},
     url = {http://alco.centre-mersenne.org/item/ALCO_2018__1_2_173_0}
}
Pilaud, Vincent; Pons, Viviane. Permutrees. Algebraic Combinatorics, Volume 1 (2018) no. 2, pp. 173-224. doi : 10.5802/alco.1. https://alco.centre-mersenne.org/item/ALCO_2018__1_2_173_0/

[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 | Article | MR 1119703 | Zbl 0742.05084

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

[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 | Article | MR 1749253 | Zbl 0958.16038

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

[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 | Article | MR 3729508 | Zbl 1375.05270

[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 | Article | MR 1935570 | Zbl 1027.05107

[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 | Article | MR 1327096 | Zbl 0831.05063

[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 | Article | MR 2142078 | Zbl 1072.05052 | Zbl 1040.05028

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

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

[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 | Article | MR 1471894 | Zbl 0881.05120

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

[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 1395667 | Zbl 0885.05111

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

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

[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 | Article | MR 1654173 | Zbl 0926.16032

[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 | Article | MR 1358493 | Zbl 0838.05100

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

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

[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)) | Article | MR 1766274 | Zbl 0960.05106

[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 | Article | MR 2734740 | Zbl 1231.05278

[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 | Article | MR 2228332 | Zbl 1110.16046

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

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

[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 1294.05191

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

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

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

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

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

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

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

[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, 19th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2007) (2007)

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

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