Combinatorial aspects of the Lascoux-Schützenberger tree. (English) Zbl 1018.05102

Little, David P.

Adv. Math. 174, No. 2, 236-253 (2003).

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)].

Reviewer: Vesselin Drensky (Sofia)

MSC:

05E05	Symmetric functions and generalizations
05E15	Combinatorial aspects of groups and algebras (MSC2010)

Keywords:

Stanley symmetric functions; Lascoux-Schützenberger tree; reduced factorizations of symmetric group; Littlewood-Richardson rule

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