Pattern avoidance and quasisymmetric functions (Q1985356)

This paper identifies several new instances of the phenomenon in algebraic combinatorics wherein certain quasisymmetric functions turn out to be symmetric and sometimes even Schur-positive. The quasisymmetric functions in question are defined as sums of Gessel's fundamental quasisymmetric functions \(F_{\operatorname{Des}\sigma}\) for \(\sigma\) ranging over certain sets of permutations, namely some pattern-avoidance classes. We recall the definitions. Let \(\mathbb{N}=\left\{ 0,1,2,\ldots\right\} \). Let \(\left[ n\right] =\left\{ 1,2,\ldots,n\right\} \) for any \(n\in\mathbb{Z}\). For any \(n\in\mathbb{N}\) and any \(D\subseteq\left[ n-1\right] \), we define a formal power series \[ F_{n,D}:=\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n};\\ i_{j}<i_{j+1}\text{ for each }j\in D}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\in\mathbb{Z}\left[ \left[ x_{1},x_{2},x_{3},\ldots\right] \right] , \] called a (Gessel) fundamental quasisymmetric function. This is a quasisymmetric function (see, e.g., [\textit{S. K. Mason}, Assoc. Women Math. Ser. 16, 239--279 (2019; Zbl 1420.05179)]). If \(D=\emptyset\) or \(D=\left[ n-1\right] \), this power series \(F_{n,D}\) is actuallysymmetric (i.e., invariant under permuting the \(x_{1},x_{2},x_{3},\ldots\)). It happens more frequently that sums of \(F_{n,D}\) over several \(D\) are symmetric; it is such results that the paper under review is concerned with. (See Table 1 in [\textit{S. Elizalde} and \textit{Y. Roichman}, J. Algebr. Comb. 45, No. 2, 363--405 (2017; Zbl 1362.05128)] for an overview of such symmetric sums.) We need some further definitions to state them. For any \(n\in\mathbb{N}\), we consider the symmetric group \(\mathfrak{S}_{n}\) of all permutations of \(\left[ n\right] :=\left\{ 1,2,\ldots,n\right\} \), and we identify these permutations \(\sigma\in\mathfrak{S}_{n}\) with the corresponding lists \(\sigma(1)\sigma\left( 2\right) \ldots\sigma(n)\) (written without parentheses around and without commas inbetween, to save space). For any permutation \(\sigma\in\mathfrak{S}_{n}\), we define the descent set \(\operatorname{Des}\sigma=\left\{ i\in\left[ n-1\right] \ \mid\ \sigma\left( i\right) >\sigma\left( i+1\right) \right\} \). A permutation \(\sigma\in\mathfrak{S}_{n}\) is said to avoid a permutation \(\pi\in\mathfrak{S}_{m}\) (as a pattern) if there exists no subsequence of \(\sigma(1)\sigma\left( 2\right) \ldots\sigma(n)\) whose entries appear in the same relative order as \(\pi(1),\pi\left( 2\right) ,\ldots,\pi(m)\) (meaning that the largest entry of this subsequence would lie in the same position in this subsequence as the largest entry of \(\pi(1)\pi\left( 2\right) \ldots\pi(m)\) lies in \(\pi(1)\pi\left( 2\right) \ldots\pi(m)\), and likewise for the second-largest entries, and so on). Given a set \(\Pi\) of permutations and a number \(n\in\mathbb{N}\), we define \(\mathfrak{S}_{n}(\Pi)\) to be the set of all permutations \(\sigma\in\mathfrak{S}_{n}\) that avoid all permutations \(\pi\in\Pi\). Sets of the form \(\mathfrak{S}_{n}(\Pi)\) are the famous pattern avoidance classes (see Chapters 4 and 5 of [\textit{M. Bóna}, Combinatorics of permutations. 2nd ed. Boca Raton, FL: CRC Press (2012; Zbl 1255.05001)] for a friendly introduction to this subject). For any set \(\Pi\) of permutations, and any \(n\in\mathbb{N}\), we define the power series \[ Q_{n}(\Pi)=\sum_{\sigma\in\mathfrak{S}_{n}(\Pi)}F_{n,\operatorname{Des}\sigma}. \] The paper identifies several sets \(\Pi\) for which this series \(Q_{n}(\Pi)\) is symmetric for all \(n\in\mathbb{N}\); for most of these sets, it is furthermore Schur-positive (i.e., a linear combination of Schur functions with nonnegative coefficients; the authors call this ``Schur nonnegative''). In particular, all subsets \(\Pi\) of \(\mathfrak{S}_{3}\) for which \(Q_{n}(\Pi)\) is symmetric are characterized. The corresponding series \(Q_{n}(\Pi)\) are all described explicitly as linear combinations of Schur functions \(s_{\lambda}\) (see, e.g., [\textit{R. P. Stanley}, Enumerative combinatorics. Volume 2. Paperback ed. Cambridge: Cambridge University Press (2001; Zbl 0978.05002)] for the notations); for example, \begin{align*} Q_{n}\left( \left\{ 123\right\} \right) & =\sum_{\lambda\text{ with }\lambda_{1}<3}f^{\lambda}s_{\lambda};\\ Q_{n}\left( \left\{ 132,213\right\} \right) & =\sum_{\lambda\text{ is a hook}}s_{\lambda};\\ Q_{n}\left( \left\{ 132,213,321\right\} \right) & =s_{n}+s_{n-1,1}, \end{align*} where \(f^{\lambda}\) denotes the number of standard tableaux of shape \(\lambda\). Further sets \(\Pi\) studied in the paper include \(\left\{ 12\cdots k\right\} \), \(\left\{ k\cdots21\right\} \), \(\mathfrak{S}_{k}\setminus\left\{ 12\cdots k\right\} \), \(\mathfrak{S}_{k}\setminus\left\{ k\cdots21\right\} \), \(\mathfrak{S}_{k}\setminus\left\{ 12\cdots k,k\cdots21\right\} \) (for a given \(k\in\mathbb{N}\)); again, the corresponding \(Q_{n}(\Pi)\) are proved to be symmetric and Schur-positive. It is shown that symmetry of \(Q_{n}(\Pi)\) (for all \(n\in\mathbb{N}\)) is preserved by shuffle products, reversal and complementation. Various more technical results are shown. The plactic monoid (see, e.g., [\textit{M. Lothaire}, Algebraic combinatorics on words. Cambridge: Cambridge University Press (2002, Zbl 1001.68093)]) shows up, as the authors show that for certain sets \(\Pi\) of permutations, the corresponding pattern avoidance classes \(\mathfrak{S}_{n}(\Pi)\) decompose as unions of Knuth equivalence classes and thus the corresponding power series \(Q_{n}(\Pi)\) are symmetric and Schur-positive. These sets \(\Pi\) are said to be pattern-Knuth closed. Some criteria for this are given in the paper; in particular, \(\left\{ 132,312\right\} \) is pattern-Knuth closed. Another set \(\Pi\) for which \(Q_{n}(\Pi)\) is always symmetric and Schur-positive is the set of arc permutations of a given size (as introduced in [\textit{S. Elizalde} and\textit{ Y. Roichman}, J. Algebr. Comb. 45, No. 2, 363--405 (2017; Zbl 1362.05128)]). Finally, an example of a set \(\Pi \subseteq\mathfrak{S}_{4}\) is constructed for which \(Q_{n}(\Pi)\) is symmetric but not Schur-positive. Several questions are left open. The work is continued in [\textit{J. S. Bloom} and \textit{B. E. Sagan}, Ann. Comb. 24, No. 2, 337--361 (2020; Zbl 1445.05109)].