Discrete Math Seminar: Justin Chan

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.