A New Class of Wilf-Equivalent Permutations

By Zvezdelina Stankova, J. West. 2001

67 citations recorded by the source corpus.

For about 10 years, the classification up to Wilf equivalence of permutation patterns was thought completed up to length 6. In this paper, we establish a new class of Wilf-equivalent permutation patterns, namely, (n − 1, n − 2, n, τ) ∼ (n − 2, n, n − 1, τ) for any τ∈Sn−3. In particular, at level n = 6, this result includes the only missing equivalence (546213) ∼ (465213), and for n = 7 it completes the classification of permutation patterns by settling all remaining cases in S7.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/0557359632278267686c605d6c8a6880cb27a03c

Citations in the corpus

• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia (2005, unknown): “Then σ occurs as a pattern in π if for some subsequence τ of π of the same length as σ all the values in τ occur in the same relative order as the corresponding values in σ.”