zbMATH — the first resource for mathematics

Order structure on the algebra of permutations and of planar binary trees. (English) Zbl 0998.05013
If $$X_n$$ is either the symmetric group on $$n$$ letters, the set of planar binary $$n$$-trees or the set of vertices of the $$(n-1)$$-dimensional cube, then $$K[X_\infty]$$ denotes the algebra $$\bigoplus_{n\geq 0} K[X_n]$$, where the product on generators $$\sigma$$ and $$\tau$$ is denoted by $$\sigma*\tau$$ and in each case can be written as $$\sigma *\tau= \sum\omega$$, where $$\sigma/\tau\leq \omega\leq\sigma\setminus\tau$$, the constructions varying for the different types although related in interesting ways via somewhat natural maps. On $$\sigma\in S_p$$, $$\tau\in S_q$$, $$\sigma/\tau= \sigma\times\tau\in S_{p+q}$$ and $$\sigma\setminus\tau= \xi_{p,q}(\sigma\times \tau)\in S_{p+q}$$ where $$\xi_{p,q}$$ is the permutation whose image is $$(q+1,\dots, q+p,1,2,\dots, q)$$ and where $$\sigma/\tau\leq \sigma\setminus\tau$$ in the weak Bruhat order for $$S_{p+q}$$, permitting a simpler description of this product and thereby an ‘easier’ analysis of the algebra $$K[S_\infty]$$. On planar binary $$n$$-trees $$u$$ and $$v$$, $$u/v$$ is the tree obtained by identifying the root of $$u$$ with the leftmost leaf of $$v$$, while $$u\setminus v$$ is obtained by identifying the rightmost leaf of $$u$$ with the root of $$v$$, while the $$(n-1)$$-cube order is the usual product order on the coordinates of the vertices. Again, this paper shows the tight intertwining of certain structures including graph theoretical ones with a cornucopia of algebraic structures each revealing in their own ways interesting properties not easily visible otherwise of which these studied here are one more useful example.

MSC:
 05C05 Trees 05A05 Permutations, words, matrices 20F55 Reflection and Coxeter groups (group-theoretic aspects) 06A99 Ordered sets
Full Text:
References:
 [1] N. Bourbaki, Groupes et algèbres de Lie, Hermann Paris 1968; reprinted Masson, Paris, 1981, Ch. 4-6. [2] Brouder, C.; Frabetti, A., Renormalization of QED with trees, Eur. Phys. J. C, 19, 715-741, (2001) · Zbl 1099.81568 [3] Gelfand, I. M.; Krob, D.; Lascoux, A.; Leclerc, B.; Retakh, V.; Thibon, J.-Y., Noncommutative symmetric functions, Adv. Math., 112, 218-348, (1995) · Zbl 0831.05063 [4] J.-L. Loday, “Dialgebras,” in Dialgebras and Related Operads, Springer Lecture Notes in Math., Vol. 1763, (2001), 7-66. · Zbl 0970.00010 [5] Loday, J.-L.; Ronco, M. O., Hopf algebra of the planar binary trees, Adv. Math., 139, 293-309, (1998) · Zbl 0926.16032 [6] Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 967-982, (1995) · Zbl 0838.05100 [7] Solomon, L., A Mackey formula in the group ring of a Coxeter group, J. Algebra, 41, 255-264, (1976) [8] R.P. Stanley, Enumerative Combinatorics, Vol. I, TheWadsworth and Brooks/Cole Mathematics Series, 1986.
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.