Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Abstract

A pattern $\tau$ is a permutation, and an arithmetic occurrence of $\tau$ in (another) permutation $\pi ={\pi }_1{\pi }_2...{\pi }_n$ is a subsequence ${\pi }_{i_1}{\pi }_{i_2}...{\pi }_{i_m}$ of $\pi$ that is order isomorphic to $\tau$ where the numbers $i_1<i_2<...<i_m$ form an arithmetic progression. A permutation is $(k,\ell )$-crucial if it avoids arithmetically the patterns $\mathrm{12...}k$ and $\ell (\ell -1)...1$ but its extension to the right by any element does not avoid arithmetically these patterns. A $(k,\ell )$-crucial permutation that cannot be extended to the left without creating an arithmetic occurrence of $\mathrm{12...}k$ or $\ell (\ell -1)...1$ is called $(k,\ell )$-bicrucial. In this paper we prove that arbitrary long $(k,\ell )$-crucial and $(k,\ell )$-bicrucial permutations exist for any $k,\ell \ge 3$. Moreover, we show that the minimal length of a $(k,\ell )$-crucial permutation is $\max (k,\ell )(\min (k,\ell )-1)$, while the minimal length of a $(k,\ell )$-bicrucial permutation is at most $2\max (k,\ell )(\min (k,\ell )-1)$, again for $k,\ell \ge 3$.