Constraining Strong c-Wilf Equivalence Using Cluster Poset Asymptotics

Abstract

Let $\pi \in {\mathfrak{S}}_m$ and $\sigma \in {\mathfrak{S}}_n$ be permutations. An occurrence of $\pi$ in $\sigma$ as a consecutive pattern is a subsequence ${\sigma }_i{\sigma }_{i+1}\cdots {\sigma }_{i+m-1}$ of $\sigma$ with the same order relations as $\pi$. We say that patterns $\pi ,\tau \in {\mathfrak{S}}_m$ are strongly c-Wilf equivalent if for all $n$ and $k$, the number of permutations in ${\mathfrak{S}}_n$ with exactly $k$ occurrences of $\pi$ as a consecutive pattern is the same as for $\tau$. In 2018, Dwyer and Elizalde conjectured (generalizing a conjecture of Elizalde from 2012) that if $\pi ,\tau \in {\mathfrak{S}}_m$ are strongly c-Wilf equivalent, then $({\tau }_1,{\tau }_m)$ is equal to one of $({\pi }_1,{\pi }_m)$, $({\pi }_m,{\pi }_1)$, $(m+1-{\pi }_1,m+1-{\pi }_m)$, or $(m+1-{\pi }_m,m+1-{\pi }_1)$. We prove this conjecture using the cluster method introduced by Goulden and Jackson in 1979, which Dwyer and Elizalde previously applied to prove that $|{\pi }_1-{\pi }_m|=|{\tau }_1-{\tau }_m|$. A consequence of our result is the full classification of c-Wilf equivalence for a special class of permutations, the non-overlapping permutations. Our approach uses analytic methods to approximate the number of linear extensions of the "cluster posets" of Elizalde and Noy.

11 pages, 3 figures