×

zbMATH — the first resource for mathematics

Combinatorial aspects of the Lascoux-Schützenberger tree. (English) Zbl 1018.05102
For a permutation \(\sigma\) of the symmetric group \(S_n\), let \(\text{Red}(\sigma)\) be the set of all reduced decompositions \(\sigma=s_{a_1}\cdots s_{a_l}\), i.e. presentations of \(\sigma\) as a product of minimal length with respect to the generators \(s_i=(i,i+1)\), \(i=1,\dots,n-1\). As an approach to the fundamental problem to determine the cardinality of \(\text{Red}(\sigma)\) for a fixed \(\sigma\), R. P. Stanley [Eur. J. Comb. 5, 359-372 (1984; Zbl 0587.20002)] introduced a function \(F_{\sigma}(X)\). He showed that \(F_{\sigma}(X)\) is symmetric and for the permutation \(\sigma=(n,n-1,\dots,1)\), the element of longest length, the number of reduced words is equal to the number of standard Young tableaux of staircase shape \((n-1,n-2,\dots,1)\). Stanley also conjectured that the symmetric function \(F_{\sigma}(X)\) is Schur positive. The conjecture was confirmed by P. Edelman and C. Green [in: Combinatorics and algebra, Proc. Conf., Boulder/Colo. 1983, Contemp. Math. 34, 155-162 (1984; Zbl 0562.05008) and Adv. Math. 63, 42-99 (1987; Zbl 0616.05005)] using the technique of balanced tableaux.
The main contribution of the paper under review is the construction of a correspondence \(\Theta_{\sigma}\) which sends the reduced decomposition \(w\in \text{Red}(\sigma)\) to a pair \((\alpha(w),T(w))\), where \(\alpha(w)\) is a Grassmanian permutation (a permutation with only one descent) and \(T(w)\) is a standard tableau of shape \(\lambda'(\alpha(w))\). The main idea is to associate a line diagram to each word \(w\) which illustrates the trajectories of the numbers \(1,2,\dots,n\) as they are rearranged by successive simple transpositions. The proof that \(\Theta_{\sigma}\) is a bijection is quite simple and its properties can be established in a straightforward manner. This gives an elementary proof of the Schur positivity of the Stanley symmetric functions. The author also obtains a simple and purely combinatorial proof of the version of the Littlewood-Richardson rule given by A. Lascoux and M.-P. Schützenberger [Lett. Math. Phys. 10, 111-124 (1985; Zbl 0586.20007)].

MSC:
05E05 Symmetric functions and generalizations
05E15 Combinatorial aspects of groups and algebras (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. Edelman, C. Greene, Combinatorial correspondences for Young tableaux, balanced tableaux, and maximal chains in the weak Bruhat order of Sn, in: Combinatorics and Algebra (Boulder, CO, 1983), Amer. Math. Soc., Providence, RI, 1984, pp. 155-162.
[2] Edelman, P.; Greene, C., Balanced tableaux, Adv. in math., 63, 1, 42-99, (1987) · Zbl 0616.05005
[3] A.M. Garsia, The saga of reduced factorizations of elements of the symmetric group, Publications du LaCIM, Université du Québec á Montréal, Canada, Vol. 29, 2002.
[4] Lascoux, A.; Schützenberger, M.-P., Schubert polynomials and the Littlewood-Richardson rule, Lett. math. phys., 10, 2-3, 111-124, (1985) · Zbl 0586.20007
[5] Stanley, R.P., On the number of reduced decompositions of elements of Coxeter groups, European J. combin., 5, 4, 359-372, (1984) · Zbl 0587.20002
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.