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.
LanguageEnglish
Pages660-671
Number of pages12
JournalSiberian Electronic Mathematical Reports
Volume9
Publication statusPublished - 19 Dec 2012

Fingerprint

Monotone
Permutation
Arithmetic sequence
Subsequence
Isomorphic
Line
Arbitrary

Keywords

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

Cite this

@article{a3267316483c4deca921439c43c82d8a,
title = "Crucial and bicrucial permutations with respect to arithmetic monotone patterns",
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 i1In 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.",
keywords = "crucial permutation, bicrucial permutation, monotone pattern, arithmetic pattern, minimal length",
author = "Sergey Avgustinovich and Sergey Kitaev and Alexander Valyuzhenich",
year = "2012",
month = "12",
day = "19",
language = "English",
volume = "9",
pages = "660--671",
journal = "Siberian Electronic Mathematical Reports",
issn = "1813-3304",
publisher = "Sobolev Institute of Mathematics",

}

Crucial and bicrucial permutations with respect to arithmetic monotone patterns. / Avgustinovich, Sergey; Kitaev, Sergey; Valyuzhenich, Alexander.

In: Siberian Electronic Mathematical Reports, Vol. 9, 19.12.2012, p. 660-671.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Crucial and bicrucial permutations with respect to arithmetic monotone patterns

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

AU - Valyuzhenich, Alexander

PY - 2012/12/19

Y1 - 2012/12/19

N2 - 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 i1In 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.

AB - 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 i1In 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.

KW - crucial permutation

KW - bicrucial permutation

KW - monotone pattern

KW - arithmetic pattern

KW - minimal length

UR - http://semr.math.nsc.ru/v9/p660-671.pdf

UR - http://semr.math.nsc.ru/v9.html

M3 - Article

VL - 9

SP - 660

EP - 671

JO - Siberian Electronic Mathematical Reports

T2 - Siberian Electronic Mathematical Reports

JF - Siberian Electronic Mathematical Reports

SN - 1813-3304

ER -