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
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},
     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, p. 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, 58 (1991) no. 1, p. 85 -114 MR 1119703 | Zbl 0742.05084 | Article

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

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

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

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

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

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

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

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

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

[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., 6 (1997) no. 4, p. 339 -376 MR 1471894 | Zbl 0881.05120 | Article

[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., 3 (1996) no. 2 MR 1395667 | Zbl 0885.05111 |

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

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

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

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

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

[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, 299 (2012) MR 3235205 | Zbl 1253.00013 | Article

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

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

[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, 299 (2006) no. 2, p. 648 -678 MR 2228332 | Zbl 1110.16046 | Article

[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, p. 1026 -1106 MR 2487491 | Zbl 1162.52007 | Article

[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, 21 (2004) no. 4, p. 315 -344 MR 2209128 | Zbl 1097.20036 | Article

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

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

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

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

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

[34] Shnider, Steve; Sternberg, Shlomo Quantum groups: From coalgebras to Drinfeld algebras, International Press, Cambridge, MA, Series in Mathematical Physics (1993) 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., 2 (2006) no. 3, p. 655 -671 MR 2252112 | Zbl 1109.52010 | Article

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