An analogue of the plactic monoid for binary search trees. (Un analogue du monoïde plaxique pour les arbres binaires de recherche.) (French) Zbl 1013.05026
Summary: We introduce a monoid structure on a certain set of labelled binary trees, by a process similar to the construction of the plactic monoid. This leads to a new interpretation of the algebra of planar binary trees of J.-L. Loday and M. O. Ronco [Adv. Math. 139, 293-309 (1998; Zbl 0926.16032) and J. Algebr. Comb. 15, 253-270 (2002; Zbl 0998.05013)].
MSC:
| 05C05 | Trees |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68P10 | Searching and sorting |
References:
| [1] | Björner, A.; Wachs, M., \(q\)-Hook length formulas for forests, J. Combin. Theory Ser. A, 52, 165-187 (1989) · Zbl 0697.06002 |
| [2] | Björner, A.; Wachs, M., Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A, 58, 85-114 (1991) · Zbl 0742.05084 |
| [3] | Duchamp, G.; Hivert, F.; Thibon, J.-Y., Une généralisation des fonctions quasi-symétriques et des fonctions symétriques non commutatives, C. R. Acad. Sci. Paris, Série I, 328, 12, 1113-1116 (1999) · Zbl 0978.05072 |
| [4] | G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput., à paraı̂tre; G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput., à paraı̂tre · Zbl 1027.05107 |
| [5] | G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VII, en préparation; G. Duchamp, F. Hivert, J.-Y. Thibon, Noncommutative symmetric functions VII, en préparation |
| [6] | Fomin, S., Duality of graded graphs, J. Algebraic Combin., 3, 357-404 (1994) · Zbl 0810.05005 |
| [7] | Frame, J. S.; de B. Robinson, G.; Thrall, R. M., The hook graphs of the symmetric groups, Canadian J. Math., 6, 316-324 (1954) · Zbl 0055.25404 |
| [8] | Knuth, D. E., The Art of Computer Programming, Vol. 3, Sorting and Searching (1973), Addison-Wesley · Zbl 0302.68010 |
| [9] | Krob, D.; Thibon, J.-Y., Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at \(q=0\), J. Algebraic Combin., 6, 4, 339-376 (1997) · Zbl 0881.05120 |
| [10] | Lascoux, A.; Schützenberger, M.-P., Le monoı̈de plaxique, (Noncommutative Structures in Algebra and Geometric Combinatorics, Naples, 1978. Noncommutative Structures in Algebra and Geometric Combinatorics, Naples, 1978, Quad. Ricerca Sci., 109 (1981), CNR: CNR Rome), 129-156 · Zbl 0517.20036 |
| [11] | Loday, J.-L.; Ronco, M. O., Hopf algebra of the planar binary trees, Adv. Math., 139, 2, 293-309 (1998) · Zbl 0926.16032 |
| [12] | Loday, J.-L.; Ronco, M. O., Order structure on the algebra of permutations and of planar binary trees, J. Algebraic Combin., 15, 3, 253-270 (2002) · Zbl 0998.05013 |
| [13] | Lothaire, M., Algebraic Combinatorics on Words (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1001.68093 |
| [14] | Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and Solomon descent algebra, J. Algebra, 177, 892-967 (1995) · Zbl 0838.05100 |
| [15] | Poirier, S.; Reutenauer, C., Algèbres de Hopf de tableaux, Ann. Sci. Math. Québec, 19, 1, 79-90 (1995) · Zbl 0835.16035 |
| [16] | Ronco, M. O., Primitive elements in a free dendriform Hopf algebra. Primitive elements in a free dendriform Hopf algebra, Contemp. Math., 267 (2000), pp. 245-264 · Zbl 0974.16035 |
| [17] | Stanley, R. P., Ordered structures and partitions, Mem. Amer. Math. Soc., 119 (1972) · Zbl 0246.05007 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
