2012/10/09 by S. V. Avgustinovich, Sergey Avgustinovich, Sergey Kitaev +4 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1210.2621
arxiv created 2012/10/09 · openalex publication_date 2012/10/09 · arxiv updated 2012/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.