×

zbMATH — the first resource for mathematics

Permutrees. (English) Zbl 1388.05039
The aim of this article is to provide a unification of several combinatorial objects (binary trees, Cambrian trees, binary sequences, permutations), respecting their poset structures (Tamari, Cambrian, Boolean and weak Bruhat lattices), their geometrical structures (associahedron, permutohedron…) and their algebraic structures (Loday-Ronco Hopf algebra, Malvenuto-Reutenauer Hopf algebras…). Permutrees are directed trees with labeled vertices respecting specific restrictions. A notion of decoration allows to give back the objects listed above.
Permutrees are given a lattice structure. A morphism from the weak Bruhat lattice of decorated permutations to permutrees is defined. It specialized to the Tamari lattice, Cambrian lattice and Boolean lattice. The Hasse graph of this lattice is given a polytope structure, called permutreehedron, obtained by deleting facted of the permutohedron. It specialized to associahedron.
A Hopf algebra structure on permutrees is defined. It contains the Malvenuto-Reutenauer and Loday-Ronco Hopf algebras, as well as the Hopf algebra on Cambrian trees defined by G. Chatel and V. Pilaud [Adv. Math. 311, 598–633 (2017; Zbl 1369.05211)] and the Hopf algebra of binary sequences defined by I. M. Gelfand et al. [Adv. Math. 112, No. 2, 218–348 (1995; Zbl 0831.05063)].

MSC:
05C05 Trees
52-04 Software, source code, etc. for problems pertaining to convex and discrete geometry
16T05 Hopf algebras and their applications
16T30 Connections of Hopf algebras with combinatorics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Björner, Anders; Wachs, Michelle L., Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A, 58, 1, 85-114, (1991) · Zbl 0742.05084
[2] Carr, Michael P.; Devadoss, Satyan L., Coxeter complexes and graph-associahedra, Topology Appl., 153, 12, 2155-2168, (2006) · Zbl 1099.52001
[3] Chapoton, Frédéric, Algèbres de Hopf des permutahèdres, associahèdres et hypercubes, Adv. Math., 150, 2, 264-275, (2000) · Zbl 0958.16038
[4] Chatel, Grégory; Pilaud, Vincent, Cambrian Hopf algebras, Adv. Math., 311, 598-633, (2017) · Zbl 1369.05211
[5] Dermenjian, Aram; Hohlweg, Christophe; Pilaud, Vincent, The facial weak order and its lattice quotients, Trans. Amer. Math. Soc., 370, 2, 1469-1507, (2018) · 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., 12, 5, 671-717, (2002) · Zbl 1027.05107
[7] Gelfand, Israel M.; Krob, Daniel; Lascoux, Alain; Leclerc, Bernard; Retakh, Vladimir S.; Thibon, Jean-Yves, Noncommutative symmetric functions, Adv. Math., 112, 2, 218-348, (1995) · Zbl 0831.05063
[8] Hivert, Florent; Novelli, Jean-Christophe; Thibon, Jean-Yves, The algebra of binary search trees, Theoret. Comput. Sci., 339, 1, 129-165, (2005) · Zbl 1040.05028
[9] Hohlweg, Christophe; Lange, Carsten, Realizations of the associahedron and cyclohedron, Discrete Comput. Geom., 37, 4, 517-543, (2007) · Zbl 1125.52011
[10] Hohlweg, Christophe; Lange, Carsten; Thomas, Hugh, Permutahedra and generalized associahedra, Adv. Math., 226, 1, 608-640, (2011) · 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)
[12] Krob, Daniel; Thibon, Jean-Yves, Noncommutative symmetric functions. IV. quantum linear groups and Hecke algebras at \(q=0\), J. Algebraic Combin., 6, 4, 339-376, (1997) · Zbl 0881.05120
[13] Lange, Carsten; Pilaud, Vincent, Associahedra via spines, (2017) · Zbl 1413.52017
[14] Lascoux, Alain; Schützenberger, Marcel-Paul, Treillis et bases des groupes de Coxeter, Electron. J. Combin., 3, 2, (1996) · Zbl 0885.05111
[15] Loday, Jean-Louis, Dialgebras and related operads, 1763, Dialgebras, 7-66, (2001), Springer, Berlin · Zbl 0999.17002
[16] Loday, Jean-Louis, Realization of the stasheff polytope, Arch. Math. (Basel), 83, 3, 267-278, (2004) · Zbl 1059.52017
[17] Loday, Jean-Louis; Ronco, María O., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309, (1998) · Zbl 0926.16032
[18] Malvenuto, Claudia; Reutenauer, Christophe, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 3, 967-982, (1995) · Zbl 0838.05100
[19] Matoušek, Jiří, Lectures on discrete geometry, 212, xvi+481 pp., (2002), Springer-Verlag, New York · Zbl 0999.52006
[20] Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim, Associahedra, Tamari Lattices and Related Structures. Tamari Memorial Festschrift, 299, xx+433 pp., (2012), Springer, New York · Zbl 1253.00013
[21] Novelli, Jean-Christophe, On the hypoplactic monoid, Discrete Math., 217, 1-3, 315-336, (2000) · 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., 310, 24, 3584-3606, (2010) · Zbl 1231.05278
[23] The On-Line Encyclopedia of Integer Sequences, (2010)
[24] Palacios, Patricia; Ronco, María O., Weak Bruhat order on the set of faces of the permutohedron and the associahedron, J. Algebra, 299, 2, 648-678, (2006) · Zbl 1110.16046
[25] Pilaud, Vincent, Signed tree associahedra, (2013)
[26] Postnikov, Alexander, Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN, 6, 1026-1106, (2009) · Zbl 1162.52007
[27] Priez, Jean-Baptiste, A lattice of combinatorial Hopf algebras, Application to binary trees with multiplicities, (2013) · Zbl 1294.05191
[28] Reading, Nathan, Lattice congruences of the weak order, Order, 21, 4, 315-344, (2004) · Zbl 1097.20036
[29] Reading, Nathan, Lattice congruences, fans and Hopf algebras, J. Combin. Theory Ser. A, 110, 2, 237-273, (2005) · Zbl 1133.20027
[30] Reading, Nathan, Cambrian lattices, Adv. Math., 205, 2, 313-353, (2006) · Zbl 1106.20033
[31] Reading, Nathan, Noncrossing arc diagrams and canonical join representations, SIAM J. Discrete Math., 29, 2, 736-750, (2015) · Zbl 1314.05015
[32] Reading, Nathan; Speyer, David E., Cambrian fans, J. Eur. Math. Soc., 11, 2, 407-447, (2009) · Zbl 1213.20038
[33] Schensted, Craige, Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191, (1961) · Zbl 0097.25202
[34] Shnider, Steve; Sternberg, Shlomo, Quantum groups: From coalgebras to Drinfeld algebras, 592 pp., (1993), International Press, Cambridge, MA · Zbl 0845.17015
[35] The Sage-Combinat community, Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, (2016)
[36] The Sage developers, Sage Mathematics Software, (2016)
[37] Viennot, Xavier, 19th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2007), Catalan tableaux and the asymmetric exclusion process, (2007)
[38] Zelevinsky, Andrei, Nested complexes and their polyhedral realizations, Pure Appl. Math. Q., 2, 3, 655-671, (2006) · Zbl 1109.52010
[39] Ziegler, Günter M., Lectures on polytopes, 152, x+370 pp., (1995), Springer-Verlag, New York · 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.