Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Sergey Avgustinovich, Sergey Kitaev, Alexander Valyuzhenich

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

A pattern τ is a permutation, and an arithmetic occurrence of τ in (another) permutation π=π1π2...πn is a subsequence πi1πi2...πim of π that is order isomorphic to τ where the numbers i1<i2<...<im 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 max(k,ℓ)(min(k,ℓ)−1), while the minimal length of a (k,ℓ)-bicrucial permutation is at most 2max(k,ℓ)(min(k,ℓ)−1), again for k,ℓ≥3.
Original languageEnglish
Pages (from-to)660-671
Number of pages12
JournalSiberian Electronic Mathematical Reports
Volume9
Publication statusPublished - 19 Dec 2012

Keywords

  • crucial permutation
  • bicrucial permutation
  • monotone pattern
  • arithmetic pattern
  • minimal length

Cite this