Crucial and bicrucial permutations with respect to arithmetic monotone patterns

الأصل · EN

A pattern τ is a permutation, and an arithmetic occurrence of τ in (another) permutation π=π₁π₂...πₙ is a subsequence πᵢ₁πᵢ₂...πᵢₘ of π that is order isomorphic to τ where the numbers i₁<i₂<...<iₘ form an arithmetic progression. A permutation is (k,ℓ)-crucial if it avoids arithmetically the patterns 12... k and ℓ(ℓ-1)... 1 but its extension to the right by any element does not avoid arithmetically these patterns. A (k,ℓ)-crucial permutation that cannot be extended to the left without creating an arithmetic occurrence of 12... k or ℓ(ℓ-1)... 1 is called (k,ℓ)-bicrucial. In this paper we prove that arbitrary long (k,ℓ)-crucial and (k,ℓ)-bicrucial permutations exist for any k,ℓ≥ 3. Moreover, we show that the minimal length of a (k,ℓ)-crucial permutation is (k,ℓ)((k,ℓ)-1), while the minimal length of a (k,ℓ)-bicrucial permutation is at most 2(k,ℓ)((k,ℓ)-1), again for k,ℓ≥3.