Given a set of permutations , let denote the set of permutations in the symmetric group that avoid every element of in the sense of pattern avoidance. Given a subset of , let be the fundamental quasisymmetric function indexed by . Our object of study is the generating function where the sum is over all and is the descent set of . We characterize those such that is symmetric or Schur nonnegative for all . In the process, we show how each of the resulting can be obtained from a theorem or conjecture involving more general sets of patterns. In particular, we prove results concerning symmetries, shuffles, and Knuth classes, as well as pointing out a relationship with the arc permutations of Elizalde and Roichman. Various conjectures and questions are mentioned throughout.
Revised: 2019-06-06
Accepted: 2019-09-17
Published online: 2020-04-01
Classification: 05E05, 05A05
Keywords: Knuth class, pattern avoidance, quasisymmetric function, Schur function, shuffle, symmetric function, Young tableau
@article{ALCO_2020__3_2_365_0, author = {Hamaker, Zachary and Pawlowski, Brendan and Sagan, Bruce E.}, title = {Pattern avoidance and quasisymmetric functions}, journal = {Algebraic Combinatorics}, pages = {365--388}, publisher = {MathOA foundation}, volume = {3}, number = {2}, year = {2020}, doi = {10.5802/alco.96}, language = {en}, url = {https://alco.centre-mersenne.org/item/ALCO_2020__3_2_365_0/} }
Hamaker, Zachary; Pawlowski, Brendan; Sagan, Bruce E. Pattern avoidance and quasisymmetric functions. Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 365-388. doi : 10.5802/alco.96. https://alco.centre-mersenne.org/item/ALCO_2020__3_2_365_0/
[1] Matrices, characters and descents, Linear Algebra Appl., Volume 469 (2015), pp. 381-418 | Article | MR 3299069 | Zbl 1305.05227
[2] Revisiting patterns avoidance and quasisymmetric functions (2018) (preprint, https://arxiv.org/abs/1812.10738)
[3] Combinatorics of permutations, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004, xiv+383 pages | Zbl 1052.05001
[4] Arc permutations, J. Algebr. Comb., Volume 39 (2014) no. 2, pp. 301-334 | Article | MR 3159254 | Zbl 1292.05268
[5] Signed arc permutations, J. Comb., Volume 6 (2015) no. 1-2, pp. 205-234 | Article | MR 3338850 | Zbl 1312.05007
[6] On rotated Schur-positive sets, J. Comb. Theory, Ser. A, Volume 152 (2017), pp. 121-137 | Article | MR 3682729 | Zbl 1369.05208
[7] Schur-positive sets of permutations via products and grid classes, J. Algebr. Comb., Volume 45 (2017) no. 2, pp. 363-405 | Article | MR 3604061 | Zbl 1362.05128
[8] A combinatorial problem in geometry, Compos. Math., Volume 2 (1935), pp. 463-470 | Numdam | MR 1556929 | Zbl 61.0651.04
[9] Multipartite -partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983) (Contemp. Math.) Volume 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289-317 | Article | MR 777705 | Zbl 0562.05007
[10] Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1995, x+475 pages (With contributions by A. Zelevinsky, Oxford Science Publications) | Zbl 0824.05059
[11] Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, Volume 177 (1995) no. 3, pp. 967-982 | Article | MR 1358493 | Zbl 0838.05100
[12] On the Representations of the Symmetric Group, Am. J. Math., Volume 60 (1938) no. 3, pp. 745-760 | Article | Zbl 0019.25102
[13] The symmetric group: Representations, combinatorial algorithms, and symmetric functions, Graduate Texts in Mathematics, Volume 203, Springer-Verlag, New York, 2001, xvi+238 pages | Zbl 0964.05070
[14] Longest increasing and decreasing subsequences, Can. J. Math., Volume 13 (1961), pp. 179-191 | Article | MR 121305 | Zbl 0097.25202
[15] Restricted permutations, Eur. J. Comb., Volume 6 (1985) no. 4, pp. 383-406 | Article | MR 829358 | Zbl 0615.05002
[16] Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, Volume 62, Cambridge University Press, Cambridge, 1999, xii+581 pages (With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin) | MR 1676282 | Zbl 0928.05001
[17] Enriched -partitions, Trans. Am. Math. Soc., Volume 349 (1997) no. 2, pp. 763-788 | Article | MR 1389788 | Zbl 0863.06005