On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns

Tools

Burstein, Alexander and Han, Tian and Kitaev, Sergey and Zhang, Philip B. (2024) On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns. The Electronic Journal of Combinatorics. ISSN 1077-8926 (In Press)

[thumbnail of Burstein-etal-EJC-2025-On-shape-Wilf-equivalence-of-certain-sets-of-partially] Text. Filename: Burstein-etal-EJC-2025-On-shape-Wilf-equivalence-of-certain-sets-of-partially.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 1 January 2099.
License: Creative Commons Attribution-NoDerivatives 4.0 logo
Download (312kB) | Request a copy

Abstract

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 gener- alized 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 pat- terns 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.

ORCID iDs

Burstein, Alexander, Han, Tian, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Zhang, Philip B.;
CORE (COnnecting REpositories)