Permutations avoiding sets of patterns with long monotone subsequences (Q2100048)

A permutation \(p\) contains the pattern (or subsequence) \(q=q_1 q_2 \cdots q_k\) if there is a \(k\)-element set of indices \(i_1 < i_2 < \cdots < i_k\) such that \(p_{i_r} < p_{i_s}\) if and only if \(q_r < q_s\). If \(p\) does not contain \(q\), then we say that \(p\) avoids \(q\). Let \(Av_n(q)\) be the number of permutations of length \(n\) that avoid the pattern \(q\), where the length of a permutation is the number of entries in it. In general, it is very difficult to compute the number \(Av_n(q)\), or to describe their sequence as \(n\) goes to infinity. However, the special case when \(q\) is the monotone increasing pattern of length \(k\) is much better understood; see for example [\textit{A. Regev}, Adv. Math. 41, 115--136 (1981; Zbl 0509.20009)]. Let \(A_k\) be the set of \(k\) patterns of length \(k\) that start with an increasing subsequence of length \(k-1\) and let \(A_{k,i} = A_k \setminus \{12\cdots (i-1)(i+1)\cdots ki\}\), that is, the set \(A_k\) with its elements ending in \(i\) removed. We say \(p\) avoids \(A_{k,i}\) if \(p\) avoids all patterns in \(A_{k,i}\) and we write \(Av_n(A_{k, i})\) for the number of such permutations of length \(n\). The goal of this paper is to determine the exponential growth rate \(L(A_{k,i})\) for the sequence \(Av_n(A_{k,i})\), for each \(i\leq k\). For \(2\leq i \leq k-1\), it is proven in Theorem 2.1 that \(L(A_{k,i}) = (k-2)^2\), so avoiding \(A_{k,i}\) is just as hard as avoiding \(12\cdots (k-1)\). For \(i=k\), it is proven in Theorem 3.1 that \(L(A_{k,k}) = (k-2)^2+1\). Case \(i=1\) is the most difficult case and thus a few conjectures and some experimental evidence are provided in this paper.