On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911884813271040 |
|---|---|
| author | Burstein, Alexander Han, Tian Kitaev, Sergey Zhang, Philip |
| author_facet | Burstein, Alexander Han, Tian Kitaev, Sergey Zhang, Philip |
| contents | We prove a conjecture of Gao and Kitaev on Wilf-equivalence of sets of patterns {12345,12354} and {45123,45213} that extends the list of 10 related conjectures proved in the literature in a series of papers. To achieve our goals, we prove generalized versions of shape-Wilf-equivalence results of Backelin, West, and Xin and use a particular result on shape-Wilf-equivalence of monotone patterns. We also derive general results on shape-Wilf-equivalence of certain classes of partially ordered patterns and use their specialization (also appearing in a paper by Bloom and Elizalde) as an essential piece in proving the conjecture. Our results allow us to show (shape-)Wilf-equivalence of large classes of sets of patterns, including 11 out of 12 classes found by Bean et al. in relation to the conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_14041 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns Burstein, Alexander Han, Tian Kitaev, Sergey Zhang, Philip Combinatorics 05A05 (Primary) 05A15, 05A19 (Secondary) We prove a conjecture of Gao and Kitaev on Wilf-equivalence of sets of patterns {12345,12354} and {45123,45213} that extends the list of 10 related conjectures proved in the literature in a series of papers. To achieve our goals, we prove generalized versions of shape-Wilf-equivalence results of Backelin, West, and Xin and use a particular result on shape-Wilf-equivalence of monotone patterns. We also derive general results on shape-Wilf-equivalence of certain classes of partially ordered patterns and use their specialization (also appearing in a paper by Bloom and Elizalde) as an essential piece in proving the conjecture. Our results allow us to show (shape-)Wilf-equivalence of large classes of sets of patterns, including 11 out of 12 classes found by Bean et al. in relation to the conjecture. |
| title | On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns |
| topic | Combinatorics 05A05 (Primary) 05A15, 05A19 (Secondary) |
| url | https://arxiv.org/abs/2405.14041 |