×

zbMATH — the first resource for mathematics

Cambrian Hopf algebras. (English) Zbl 1369.05211
Summary: Cambrian trees are oriented and labeled trees which fulfill local conditions around each node generalizing the classical conditions for binary search trees. Similar to binary trees for the Tamari lattice, Cambrian trees provide convenient combinatorial models for N. Reading’s Cambrian lattices of type \(A\). Based on a natural surjection from signed permutations to Cambrian trees, we define the Cambrian Hopf algebra extending J.-L. Loday and M. Ronco’s algebra on binary trees. We describe combinatorially the products and coproducts of both the Cambrian algebra and its dual in terms of operations on Cambrian trees. We then construct the Baxter-Cambrian algebra which extends S. Law and N. Reading’s Baxter Hopf algebra on rectangulations and S. Giraudo’s equivalent Hopf algebra on twin binary trees.

MSC:
05E15 Combinatorial aspects of groups and algebras (MSC2010)
16T05 Hopf algebras and their applications
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bergeron, F.; Préville-Ratelle, L.-F., Higher trivariate diagonal harmonics via generalized Tamari posets, J. Comb., 3, 3, 317-341, (2012) · Zbl 1291.05213
[2] Bonichon, N.; Bousquet-Mélou, M.; Fusy, É., Baxter permutations and plane bipolar orientations, Sém. Lothar. Combin., 61A, (2009/11), 29 pp · Zbl 1205.05004
[3] Bousquet-Mélou, M.; Fusy, É.; Préville-Ratelle, L.-F., The number of intervals in the m-Tamari lattices, Electron. J. Combin., 18, 2, (2011), 26 pp
[4] Bousquet-Mélou, M.; Chapuy, G.; Préville-Ratelle, L.-F., The representation of the symmetric group on m-Tamari intervals, Adv. Math., 247, 309-342, (2013) · Zbl 1283.05268
[5] Carr, M. P.; Devadoss, S. L., Coxeter complexes and graph-associahedra, Topology Appl., 153, 12, 2155-2168, (2006) · Zbl 1099.52001
[6] Chatel, G.; Pilaud, V., Cambrian Hopf algebras, (2014), preprint · Zbl 1335.05212
[7] Chung, F. R.K.; Graham, R. L.; Hoggatt, V. E.; Kleiman, M., The number of Baxter permutations, J. Combin. Theory Ser. A, 24, 3, 382-394, (1978) · Zbl 0398.05003
[8] Devadoss, S. L., A realization of graph associahedra, Discrete Math., 309, 1, 271-276, (2009) · Zbl 1189.05176
[9] Dulucq, S.; Guibert, O., Stack words, standard tableaux and Baxter permutations, (Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics, New Brunswick, NJ, 1994, vol. 157, (1996)), 91-106 · Zbl 0870.05077
[10] Dulucq, S.; Guibert, O., Baxter permutations, (Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics, Noisy-le-Grand, 1995, vol. 180, (1998)), 143-156 · Zbl 0895.05002
[11] Feichtner, E. M.; Sturmfels, B., Matroid polytopes, nested sets and Bergman fans, Port. Math., 62, 4, 437-468, (2005) · Zbl 1092.52006
[12] Felsner, S.; Fusy, É.; Noy, M.; Orden, D., Bijections for Baxter families and related objects, J. Combin. Theory Ser. A, 118, 3, 993-1020, (2011) · Zbl 1238.05010
[13] Gelfand, I. M.; Krob, D.; Lascoux, A.; Leclerc, B.; Retakh, V. S.; Thibon, J.-Y., Noncommutative symmetric functions, Adv. Math., 112, 2, 218-348, (1995) · Zbl 0831.05063
[14] Gessel, I.; Viennot, G., Binomial determinants, paths, and hook length formulae, Adv. Math., 58, 3, 300-321, (1985) · Zbl 0579.05004
[15] Giraudo, S., Algebraic and combinatorial structures on pairs of twin binary trees, J. Algebra, 360, 115-157, (2012) · Zbl 1253.05146
[16] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., The algebra of binary search trees, Theoret. Comput. Sci., 339, 1, 129-165, (2005) · Zbl 1072.05052
[17] Hohlweg, C.; Lange, C., Realizations of the associahedron and cyclohedron, Discrete Comput. Geom., 37, 4, 517-543, (2007) · Zbl 1125.52011
[18] Hohlweg, C.; Lange, C.; Thomas, H., Permutahedra and generalized associahedra, Adv. Math., 226, 1, 608-640, (2011) · Zbl 1233.20035
[19] Igusa, K.; Ostroff, J., Mixed cobinary trees, (2013), preprint · Zbl 1395.05189
[20] Lange, C.; Pilaud, V., Associahedra via spines, Combinatorica, (2013), in press · Zbl 1413.52017
[21] Law, S.; Reading, N., The Hopf algebra of diagonal rectangulations, J. Combin. Theory Ser. A, 119, 3, 788-824, (2012) · Zbl 1246.16027
[22] Loday, J.-L., Realization of the stasheff polytope, Arch. Math. (Basel), 83, 3, 267-278, (2004) · Zbl 1059.52017
[23] Loday, J.-L.; Ronco, M. O., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309, (1998) · Zbl 0926.16032
[24] Mallows, C. L., Baxter permutations rise again, J. Combin. Theory Ser. A, 27, 3, 394-396, (1979) · Zbl 0427.05005
[25] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 3, 967-982, (1995) · Zbl 0838.05100
[26] (Müller-Hoissen, F.; Pallo, J. M.; Stasheff, J., Associahedra, Tamari Lattices and Related Structures. Tamari Memorial Festschrift, Progress in Mathematics, vol. 299, (2012), Springer New York) · Zbl 1253.00013
[27] Novelli, J.-C., m-dendriform algebras, (2014), preprint
[28] Novelli, J.-C.; Thibon, J.-Y., 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
[29] Novelli, J.-C.; Thibon, J.-Y., Hopf algebras of m-permutations, \((m + 1)\)-ary trees, and m-parking functions, (2014), preprint
[30] Postnikov, A., Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN, 6, 1026-1106, (2009) · Zbl 1162.52007
[31] Postnikov, A.; Reiner, V.; Williams, L. K., Faces of generalized permutohedra, Doc. Math., 13, 207-273, (2008) · Zbl 1167.05005
[32] Reading, N., Lattice congruences, fans and Hopf algebras, J. Combin. Theory Ser. A, 110, 2, 237-273, (2005) · Zbl 1133.20027
[33] Reading, N., Cambrian lattices, Adv. Math., 205, 2, 313-353, (2006) · Zbl 1106.20033
[34] Reading, N.; Speyer, D. E., Cambrian fans, J. Eur. Math. Soc. (JEMS), 11, 2, 407-447, (2009) · Zbl 1213.20038
[35] The On-Line Encyclopedia of Integer Sequences. Published electronically at: http://oeis.org. · Zbl 1044.11108
[36] Viennot, G., A bijective proof for the number of Baxter permutations, (3rd Seminaire Lotharingien de Combinatoire, Le Klebach, (1981))
[37] Viennot, X., Catalan tableaux and the asymmetric exclusion process, (19th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2007, (2007))
[38] Yao, B.; Chen, H.; Cheng, C.-K.; Graham, R., Floorplan representations: complexity and connections, ACM Trans. Des. Automat. Electron. Syst., 8, 1, 55-80, (2003)
[39] Zelevinsky, A., Nested complexes and their polyhedral realizations, Pure Appl. Math. Q., 2, 3, 655-671, (2006) · Zbl 1109.52010
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.