Combinatorial aspects of the Lascoux-Schützenberger tree (Q1869992)

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\), \textit{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 \textit{P. Edelman} and \textit{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 \textit{A. Lascoux} and \textit{M.-P. Schützenberger} [Lett. Math. Phys. 10, 111-124 (1985; Zbl 0586.20007)].