Shape-Wilf-Ordering on Permutations of Length 3

Abstract

The research on pattern-avoidance has yielded so far limited knowledge on Wilf-ordering of permutations. The Stanley-Wilf limits $\lim_{n\rightarrow \infty} \sqrt[n]{|S_n(\tau)|}$ and further works suggest asymptotic ordering of layered versus monotone patterns. Yet, Bóna has provided essentially the only known up to now result of its type on complete ordering of $S_k$ for $k=4$: $|S_n(1342)| < |S_n(1234)| < |S_n(1324)|$ for $n\geq 7$, along with some other sporadic examples in Wilf-ordering. We give a different proof of this result by ordering $S_3$ up to the stronger shape-Wilf-order: $|S_Y(213)|\leq |S_Y(123)|\leq |S_Y(312)|$ for any Young diagram $Y$, derive as a consequence that $|S_Y(k+2,k+1,k+3,\tau)|\leq |S_Y(k+1,k+2,k+3,\tau)|\leq |S_Y(k+3,k+1,k+2,\tau)|$ for any $\tau\in S_k$, and find out when equalities are obtained. (In particular, for specific $Y$'s we find out that $|S_Y(123)|=|S_Y(312)|$ coincide with every other Fibonacci term.) This strengthens and generalizes Bóna's result to arbitrary length permutations. While all length-3 permutations have been shown in numerous ways to be Wilf-equivalent, the current paper distinguishes between and orders these permutations by employing all Young diagrams. This opens up the question of whether shape-Wilf-ordering of permutations, or some generalization of it, is not the "true" way of approaching pattern-avoidance ordering.