Browse issues
no. 3
Schur-positivity of short chords in matchings
Marmor, Avichai1
1 Department of Mathematics Bar-Ilan University Ramat-Gan 52900 Israel
Algebraic Combinatorics, Volume 7 (2024) no. 3, pp. 887-914.

We prove that the set of matchings with a fixed number of unmatched vertices is Schur-positive with respect to the set of short chords. Two proofs are presented. The first proof applies a new combinatorial criterion for Schur-positivity, while the second is bijective. The coefficients in the Schur expansion are derived, and interpreted in terms of Bessel polynomials. Then, we present a variant of Knuth equivalence for matchings, and show that every equivalence class corresponds to a Schur function. We proceed to find various refined Schur-positive sets, including the set of matchings with a prescribed crossing number and the set of matchings with a given number of pairs of intersecting chords. Finally, we characterize all the matchings m such that the set of matchings avoiding m is Schur-positive.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.351
Classification: 20C30, 05A19, 05E05
Keywords: Quasi-symmetric function, Schur-positive set, symmetric function, pattern avoidance, matchings, Bessel polynomials

Marmor, Avichai 1

1 Department of Mathematics Bar-Ilan University Ramat-Gan 52900 Israel
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2024__7_3_887_0,
     author = {Marmor, Avichai},
     title = {Schur-positivity of short chords in matchings},
     journal = {Algebraic Combinatorics},
     pages = {887--914},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {3},
     year = {2024},
     doi = {10.5802/alco.351},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.351/}
}
TY  - JOUR
AU  - Marmor, Avichai
TI  - Schur-positivity of short chords in matchings
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 887
EP  - 914
VL  - 7
IS  - 3
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.351/
DO  - 10.5802/alco.351
LA  - en
ID  - ALCO_2024__7_3_887_0
ER  - 
%0 Journal Article
%A Marmor, Avichai
%T Schur-positivity of short chords in matchings
%J Algebraic Combinatorics
%D 2024
%P 887-914
%V 7
%N 3
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.351/
%R 10.5802/alco.351
%G en
%F ALCO_2024__7_3_887_0
Marmor, Avichai. Schur-positivity of short chords in matchings. Algebraic Combinatorics, Volume 7 (2024) no. 3, pp. 887-914. doi : 10.5802/alco.351. https://alco.centre-mersenne.org/articles/10.5802/alco.351/

[1] Adin, Ron M.; Berenstein, Arkady; Greenstein, Jacob; Li, Jian-Rong; Marmor, Avichai; Roichman, Yuval Transitive and Gallai colorings, 2023 | arXiv

[2] Adin, Ron M.; Postnikov, Alexander; Roichman, Yuval Combinatorial Gelfand models, J. Algebra, Volume 320 (2008) no. 3, pp. 1311-1325 | DOI | MR | Zbl

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

[4] Avni, Amichai Matchings and permutations, M.Sc. thesis, Bar-Ilan University (2013)

[5] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv+363 pages | MR

[6] Bloom, Jonathan; Elizalde, Sergi Pattern avoidance in matchings and partitions, Electron. J. Combin., Volume 20 (2013) no. 2, Paper no. 5, 38 pages | DOI | MR | Zbl

[7] Bloom, Jonathan S.; Sagan, Bruce E. Revisiting pattern avoidance and quasisymmetric functions, Ann. Comb., Volume 24 (2020) no. 2, pp. 337-361 | DOI | MR | Zbl

[8] Cameron, Naiomi T.; Killpatrick, Kendra Statistics on linear chord diagrams, Discrete Math. Theor. Comput. Sci., Volume 21 (2019) no. 2, Paper no. 11, 10 pages | MR

[9] Cervetti, Matteo; Ferrari, Luca Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset, Ann. Comb., Volume 26 (2022) no. 4, pp. 971-995 | DOI | MR | Zbl

[10] Deodhar, Rajendra S.; Srinivasan, Murali K. A statistic on involutions, J. Algebraic Combin., Volume 13 (2001) no. 2, pp. 187-198 | DOI | MR | Zbl

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

[12] Fang, Jonathan J.; Hamaker, Zachary; Troyka, Justin M. On pattern avoidance in matchings and involutions, Electron. J. Combin., Volume 29 (2022) no. 1, Paper no. 1.39, 22 pages | DOI | MR | Zbl

[13] 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

[14] Gessel, Ira M.; Reutenauer, Christophe Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A, Volume 64 (1993) no. 2, pp. 189-215 | DOI | MR | Zbl

[15] Grosswald, Emil Bessel polynomials, Lecture Notes in Mathematics, 698, Springer, Berlin, 1978, xiv+182 pages | DOI | MR

[16] Hamaker, Zachary; Pawlowski, Brendan; Sagan, Bruce E. Pattern avoidance and quasisymmetric functions, Algebr. Comb., Volume 3 (2020) no. 2, pp. 365-388 | DOI | Numdam | MR | Zbl

[17] Hultman, Axel Twisted identities in Coxeter groups, J. Algebraic Combin., Volume 28 (2008) no. 2, pp. 313-332 | DOI | MR | Zbl

[18] Jelínek, Vít; Mansour, Toufik Matchings and partial patterns, Electron. J. Combin., Volume 17 (2010) no. 1, Paper no. 158, 30 pages | DOI | MR | Zbl

[19] Knuth, Donald E. Permutations, matrices, and generalized Young tableaux, Pacific J. Math., Volume 34 (1970), pp. 709-727 | DOI | MR | Zbl

[20] Mansour, Toufik; Shattuck, Mark Partial matchings and pattern avoidance, Appl. Anal. Discrete Math., Volume 7 (2013) no. 1, pp. 25-50 | DOI | MR | Zbl

[21] Marmor, Avichai Tight lower bound for pattern avoidance Schur-positivity, 2022 | arXiv

[22] McGovern, William M. Closures of O n -orbits in the flag variety for GL n , Representations and nilpotent orbits of Lie algebraic systems (Progr. Math.), Volume 330, Birkhäuser/Springer, Cham, 2019, pp. 411-419 | DOI | MR | Zbl

[23] McSorley, John P.; Feinsilver, Philip A combinatorial interpretation of Bessel polynomials and their first derivatives as ordered hit polynomials, J. Combin. Math. Combin. Comput., Volume 39 (2001), pp. 33-48 | MR | Zbl

[24] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2023 (Published electronically at http://oeis.org)

[25] Richardson, R. W.; Springer, T. A. The Bruhat order on symmetric varieties, Geom. Dedicata, Volume 35 (1990) no. 1-3, pp. 389-436 | DOI | MR | Zbl

[26] 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 | DOI | MR

[27] Sagan, Bruce E. Pattern avoidance and quasisymmetric functions, The 13th International Permutation Patterns Conference, London, UK (2015)

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

Cited by Sources: