کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653366 | 1632775 | 2015 | 20 صفحه PDF | دانلود رایگان |
Wilf-equivalence is one of the central concepts of pattern-avoiding permutations, and has been studied for more than thirty years. The two known infinite families of Wilf-equivalent permutation pairs, due to Stankova–West and Backelin–West–Xin, both satisfy the stronger condition of shape-Wilf-equivalence. Dokos et al. recently studied a different strengthening of Wilf-equivalence called inv-Wilf-equivalence, which takes account of the inversion number of a permutation. They conjectured that all inv-Wilf-equivalent permutation pairs arise from trivial symmetries. We disprove this conjecture by constructing an infinite family of counterexamples derived from the permutation pair 231 and 312. The key to this construction is to generalize simultaneously the concepts of shape-Wilf-equivalence and inv-Wilf-equivalence. A further consequence is a proof of the recent Baxter–Jaggard conjecture on even-shape-Wilf-equivalent permutation pairs.
Journal: European Journal of Combinatorics - Volume 44, Part A, February 2015, Pages 57–76