Pattern avoidance and quasisymmetric functions

Hamaker, Zachary; Pawlowski, Brendan; Sagan, Bruce E.

doi:10.5802/alco.96

Hamaker, Zachary ¹; Pawlowski, Brendan ²; Sagan, Bruce E.³

¹ University of Florida Department of Mathematics Gainesville FL 32611-1941, USA
² University of Southern California Department of Mathematics Los Angeles CA 90089-2532, USA
³ Michigan State University Department of Mathematics East Lansing MI 48824-1027, USA

Algebraic Combinatorics, Volume 3 (2020) no. 2, pp. 365-388.

Abstract

Given a set of permutations $Π$ , let $𝔖_{n} (Π)$ denote the set of permutations in the symmetric group $𝔖_{n}$ that avoid every element of $Π$ in the sense of pattern avoidance. Given a subset $S$ of ${1, \dots, n - 1}$ , let $F_{S}$ be the fundamental quasisymmetric function indexed by $S$ . Our object of study is the generating function $Q_{n} (Π) = \sum F_{Des σ}$ where the sum is over all $σ \in 𝔖_{n} (Π)$ and $Des σ$ is the descent set of $σ$ . We characterize those $Π \subseteq 𝔖_{3}$ such that $Q_{n} (Π)$ is symmetric or Schur nonnegative for all $n$ . 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.

Received: 2018-10-26
Revised: 2019-06-07
Accepted: 2019-09-18
Published online: 2020-04-01

DOI: 10.5802/alco.96

Classification: 05E05, 05A05
Keywords: Knuth class, pattern avoidance, quasisymmetric function, Schur function, shuffle, symmetric function, Young tableau

Author's affiliations:

Hamaker, Zachary ¹; Pawlowski, Brendan ²; Sagan, Bruce E. ³

¹ University of Florida Department of Mathematics Gainesville FL 32611-1941, USA
² University of Southern California Department of Mathematics Los Angeles CA 90089-2532, USA
³ Michigan State University Department of Mathematics East Lansing MI 48824-1027, USA

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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/articles/10.5802/alco.96/}
}

TY  - JOUR
AU  - Hamaker, Zachary
AU  - Pawlowski, Brendan
AU  - Sagan, Bruce E.
TI  - Pattern avoidance and quasisymmetric functions
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 365
EP  - 388
VL  - 3
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.96/
DO  - 10.5802/alco.96
LA  - en
ID  - ALCO_2020__3_2_365_0
ER  -

%0 Journal Article
%A Hamaker, Zachary
%A Pawlowski, Brendan
%A Sagan, Bruce E.
%T Pattern avoidance and quasisymmetric functions
%J Algebraic Combinatorics
%D 2020
%P 365-388
%V 3
%N 2
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.96/
%R 10.5802/alco.96
%G en
%F 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/articles/10.5802/alco.96/

References
Cited by

[1] Adin, Ron M.; Roichman, Yuval Matrices, characters and descents, Linear Algebra Appl., Volume 469 (2015), pp. 381-418 | DOI | MR | Zbl

[2] Bloom, Jonathan; Sagan, Bruce E. Revisiting patterns avoidance and quasisymmetric functions (2018) (preprint, https://arxiv.org/abs/1812.10738)

[3] Bóna, Miklós Combinatorics of permutations, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004, xiv+383 pages | MR | Zbl

[4] Elizalde, Sergi; Roichman, Yuval Arc permutations, J. Algebr. Comb., Volume 39 (2014) no. 2, pp. 301-334 | DOI | MR | Zbl

[5] Elizalde, Sergi; Roichman, Yuval Signed arc permutations, J. Comb., Volume 6 (2015) no. 1-2, pp. 205-234 | DOI | MR | Zbl

[6] Elizalde, Sergi; Roichman, Yuval On rotated Schur-positive sets, J. Comb. Theory, Ser. A, Volume 152 (2017), pp. 121-137 | DOI | MR | Zbl

[7] Elizalde, Sergi; Roichman, Yuval Schur-positive sets of permutations via products and grid classes, J. Algebr. Comb., Volume 45 (2017) no. 2, pp. 363-405 | DOI | MR | Zbl

[8] Erdős, Paul; Szekeres, George A combinatorial problem in geometry, Compos. Math., Volume 2 (1935), pp. 463-470 | Numdam | MR | Zbl

[9] Gessel, Ira M. Multipartite $P$ -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 | DOI | MR | Zbl

[10] Macdonald, Ian G. 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) | MR | Zbl

[11] Malvenuto, Claudia; Reutenauer, Christophe Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, Volume 177 (1995) no. 3, pp. 967-982 | DOI | MR | Zbl

[12] Robinson, Gilbert de B. On the Representations of the Symmetric Group, Am. J. Math., Volume 60 (1938) no. 3, pp. 745-760 | DOI | MR | Zbl

[13] Sagan, Bruce E. The symmetric group: Representations, combinatorial algorithms, and symmetric functions, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages | MR | Zbl

[14] Schensted, Craige E. Longest increasing and decreasing subsequences, Can. J. Math., Volume 13 (1961), pp. 179-191 | DOI | MR | Zbl

[15] Simion, Rodica; Schmidt, Frank W. Restricted permutations, Eur. J. Comb., Volume 6 (1985) no. 4, pp. 383-406 | DOI | MR | Zbl

[16] Stanley, Richard P. Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+581 pages (With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin) | MR | Zbl

[17] Stembridge, John R. Enriched $P$ -partitions, Trans. Am. Math. Soc., Volume 349 (1997) no. 2, pp. 763-788 | DOI | MR | Zbl

Cited by Sources: