Picture of neon light reading 'Open'

Discover open research at Strathprints as part of International Open Access Week!

23-29 October 2017 is International Open Access Week. The Strathprints institutional repository is a digital archive of Open Access research outputs, all produced by University of Strathclyde researchers.

Explore recent world leading Open Access research content this Open Access Week from across Strathclyde's many research active faculties: Engineering, Science, Humanities, Arts & Social Sciences and Strathclyde Business School.

Explore all Strathclyde Open Access research outputs...

Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Avgustinovich, Sergey and Kitaev, Sergey and Valyuzhenich, Alexander (2012) Crucial and bicrucial permutations with respect to arithmetic monotone patterns. Siberian Electronic Mathematical Reports, 9. pp. 660-671.

Full text not available in this repository. Request a copy from the Strathclyde author

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.