×

Lattice congruences, fans and Hopf algebras. (English) Zbl 1133.20027

Summary: We give a unified explanation of the geometric and algebraic properties of two well-known maps, one from permutations to triangulations, and another from permutations to subsets. Furthermore we give a broad generalization of the maps. Specifically, for any lattice congruence of the weak order on a Coxeter group we construct a complete fan of convex cones with strong properties relative to the corresponding lattice quotient of the weak order. We show that if a family of lattice congruences on the symmetric groups satisfies certain compatibility conditions then the family defines a sub-Hopf algebra of the Malvenuto-Reutenauer Hopf algebra of permutations. Such a sub-Hopf algebra has a basis which is described by a type of pattern avoidance. Applying these results, we build the Malvenuto-Reutenauer algebra as the limit of an infinite sequence of smaller algebras, where the second algebra in the sequence is the Hopf algebra of non-commutative symmetric functions. We also associate both a fan and a Hopf algebra to a set of permutations which appears to be equinumerous with the Baxter permutations.

MSC:

20F55 Reflection and Coxeter groups (group-theoretic aspects)
05E05 Symmetric functions and generalizations
06A07 Combinatorics of partially ordered sets
06B10 Lattice ideals, congruence relations
16W30 Hopf algebras (associative rings and algebras) (MSC2000)
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)

Software:

OEIS
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] M. Aguiar, N. Bergeron, F. Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville equations, preprint, 2003. · Zbl 1092.05070
[2] Aguiar, M.; Sottile, F., Structure of the malvenuto – reutenauer Hopf algebra of permutations, Adv. math., 191, 2, 225-275, (2005) · Zbl 1056.05139
[3] Billera, L.; Sturmfels, B., Fiber polytopes, Ann. math. (2), 135, 3, 527-549, (1992) · Zbl 0762.52003
[4] Billera, L.; Sturmfels, B., Iterated fiber polytopes, Mathematika, 41, 2, 348-363, (1994) · Zbl 0819.52010
[5] A. Björner, Orderings of Coxeter groups, Combinatorics and Algebra, Boulder, CO, 1983, pp. 175-195; Contemp. Math. 34.
[6] Björner, A., Posets, regular CW complexes and Bruhat order, European J. combin., 5, 1, 7-16, (1984) · Zbl 0538.06001
[7] A. Björner, Topological methods, Handbook of Combinatorics, vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 1819-1872.
[8] Björner, A.; Edelman, P.; Ziegler, G., Hyperplane arrangements with a lattice of regions, Discrete comput. geom., 5, 263-288, (1990) · Zbl 0698.51010
[9] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, second ed., Cambridge University Press, Cambridge, 1999.
[10] Björner, A.; Wachs, M., Generalized quotients in Coxeter groups, Trans. amer. math. soc., 308, 1, 1-37, (1988) · Zbl 0659.05007
[11] Björner, A.; Wachs, M., Shellable nonpure complexes and posets II, Trans. amer. math. soc., 349, 10, 3945-3975, (1997) · Zbl 0886.05126
[12] N. Bourbaki, Lie groups and Lie algebras. Translated from the 1968 French original by Andrew Pressley, Elements of Mathematics, Springer, Berlin, 2002 (Chapters 4-6).
[13] Bruggesser, H.; Mani, P., Shellable decompositions of cells and spheres, Math. scand., 29, 197-205, (1971) · Zbl 0251.52013
[14] N. Caspard, C. Le Conte de Poly-Barbut, M. Morvan, Cayley lattices of finite Coxeter groups are bounded, Adv. Appl. Math. 33 (1) (2004) 71-94. · Zbl 1097.06001
[15] Chajda, I.; Snášel, V., Congruences in ordered sets, Math. bohem., 123, 1, 95-100, (1998) · Zbl 0897.06004
[16] Chung, F.; Graham, R.; Hoggatt, V.; Kleiman, M., The number of Baxter permutations, J. combin. theory ser. A, 24, 3, 382-394, (1978) · Zbl 0398.05003
[17] Day, A., Congruence normalitythe characterization of the doubling class of convex sets, Algebra universalis, 31, 3, 397-406, (1994) · Zbl 0804.06006
[18] 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
[19] Edelman, P., A partial order on the regions of \(\mathbb{R}^n\) dissected by hyperplanes, Trans. amer. math. soc., 283, 2, 617-631, (1984) · Zbl 0555.06003
[20] Edelman, P.; Walker, J., The homotopy type of hyperplane posets, Proc. amer. math. soc., 94, 2, 221-225, (1985) · Zbl 0565.06001
[21] S. Fomin, A. Zelevinsky, Y-systems and generalized associahedra, Ann. Math. 158 (3) (2003) 977-1018. · Zbl 1057.52003
[22] R. Freese, J. Ježek, J. Nation, Free lattices, Mathematical Surveys and Monographs, vol. 42, American Mathematical Society, Providence, RI, 1995.
[23] Funayama, N.; Nakayama, T., On the distributivity of a lattice of lattice-congruences, Proc. imp. acad. Tokyo, 18, 553-554, (1942) · Zbl 0063.01483
[24] Gelfand, I.; Krob, D.; Lascoux, A.; Leclerc, B.; Retakh, V.; Thibon, J.-Y., Noncommutative symmetric functions, Adv. math., 112, 2, 218-348, (1995) · Zbl 0831.05063
[25] Grätzer, G., General lattice theory, (1998), Birkhäuser Verlag Basel · Zbl 0385.06015
[26] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., Un analogue du monoı¨de plaxique pour LES arbres binaires de recherche, C. R. math. acad. sci. Paris, 335, 7, 577-580, (2002) · Zbl 1013.05026
[27] F. Hivert, J.-C. Novelli, J.-Y. Thibon, The Algebra of Binary Search Trees, preprint , 2004. · Zbl 1072.05052
[28] J. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. · Zbl 0725.20028
[29] S. Joni, G.-C. Rota, Coalgebras and bialgebras in combinatorics, Umbral calculus and Hopf Algebras, Norman, OK, 1978, pp. 1-47; Contemp. Math. 6, 1982. · Zbl 0491.05021
[30] Kalai, G., A simple way to tell a simple polytope from its graph, J. combin. theory ser. A, 49, 2, 381-383, (1988) · Zbl 0673.05087
[31] Le Conte de Poly-Barbut, C., Sur LES treillis de Coxeter finis (French), Math. inf. sci. hum., 32, 125, 41-57, (1994) · Zbl 0802.06016
[32] Leung, N.; Reiner, V., The signature of a toric variety, Duke math. J., 111, 2, 253-286, (2002) · Zbl 1062.14067
[33] Loday, J.-L.; Ronco, M., Hopf algebra of planar binary trees, Adv. math., 139, 2, 293-309, (1998) · Zbl 0926.16032
[34] Loday, J.-L.; Ronco, M., Order structure on the algebra of permutations and of planar binary trees, J. algebraic combin., 15, 3, 253-270, (2002) · Zbl 0998.05013
[35] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. algebra, 177, 3, 967-982, (1995) · Zbl 0838.05100
[36] Milnor, J.; Moore, J., On the structure of Hopf algebras, Ann. math. (2), 81, 211-264, (1965) · Zbl 0163.28202
[37] P. Orlik, H. Terao, Arrangements of hyperplanes, Grundlehren der Mathematischen Wissenschaften, vol. 300, Springer, Berlin, 1992. · Zbl 0757.55001
[38] Reading, N., Order dimension, strong Bruhat order and lattice properties for posets, Order, 19, 1, 73-100, (2002) · Zbl 1007.05097
[39] Reading, N., Lattice and order properties of the poset of regions in a hyperplane arrangement, Algebra universalis, 50, 2, 179-205, (2003) · Zbl 1092.06006
[40] Reading, N., The order dimension of the poset of regions in a hyperplane arrangement, J. combin. theory ser. A, 104, 2, 265-285, (2003) · Zbl 1044.52010
[41] N. Reading, Lattice congruences of the weak order, preprint, 2004. · Zbl 1097.20036
[42] N. Reading, Cambrian lattices, preprint, 2004. · Zbl 1106.20033
[43] N.J.A. Sloane, (Ed.), The On-Line Encyclopedia of Integer Sequences, 2004, Published electronically at \(\sim\). · Zbl 1274.11001
[44] R. Stanley, Enumerative Combinatorics, vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997.
[45] M. Sweedler, Hopf algebras, Mathematics Lecture Note Series, W.A. Benjamin, Inc., New York, 1969.
[46] H. Thomas, Tamari Lattices for types B and D, preprint, 2003.
[47] A. Tonks, Relating the associahedron and the permutohedron, Operads: Proceedings of Renaissance Conferences, Hartford, CT/Luminy, 1995, pp. 33-36, Contemp. Math. 202, 1997. · Zbl 0873.51016
[48] West, J., Generating trees and forbidden subsequences, Discrete math., 157, 1-3, 363-374, (1996) · Zbl 0877.05002
[49] Wilf, H., The patterns of permutations kleitman and combinatoricsa celebration, Discrete math., 257, 2-3, 575-583, (2002)
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.