Crucial and bicrucial permutations with respect to arithmetic monotone patterns

zbMATH Open1330.68228arXiv1210.2621MaRDI QIDQ890954FDOQ890954

Authors: Sergey Kitaev, Sergey Avgustinovich, Alexandr Valyuzhenich 

Publication date: 16 November 2015

Published in: Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Abstract: A pattern $au$ is a permutation, and an arithmetic occurrence of $au$ in (another) permutation $pi=p{i}_{1}p{i}_2\mathrm{...}p{i}_n$ is a subsequence $p{i}_{i_1}p{i}_{i_2}\mathrm{...}p{i}_{i_m}$ of $pi$ that is order isomorphic to $au$ where the numbers $i_1<i_2<\mathrm{...}<i_m$ form an arithmetic progression. A permutation is $(k,ell)$-crucial if it avoids arithmetically the patterns $\mathrm{12...}k$ and $ell(ell-1)\mathrm{...1}$ but its extension to the right by any element does not avoid arithmetically these patterns. A $(k,ell)$-crucial permutation that cannot be extended to the left without creating an arithmetic occurrence of $\mathrm{12...}k$ or $ell(ell-1)\mathrm{...1}$ is called $(k,ell)$-bicrucial. In this paper we prove that arbitrary long $(k,ell)$-crucial and $(k,ell)$-bicrucial permutations exist for any $k,ellgeq3$. Moreover, we show that the minimal length of a $(k,ell)$-crucial permutation is $max(k,ell)(min(k,ell)-1)$, while the minimal length of a $(k,ell)$-bicrucial permutation is at most $2max(k,ell)(min(k,ell)-1)$, again for $k,ellgeq3$.

Full work available at URL: https://arxiv.org/abs/1210.2621

Recommendations

• On five types of crucial permutations with respect to monotone patterns
• On permutations avoiding arithmetic progressions
• \(S\)-crucial and bicrucial permutations with respect to squares
• The lengths for which bicrucial square-free permutations exist
• Antimonotone permutations

zbMATH Keywords

minimal lengtharithmetic patternbicrucial permutationcrucial permutationmonotone pattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15) Automata sequences (11B85)

Cited In (5)

• The lengths for which bicrucial square-free permutations exist
• Permutations with exactly one copy of a monotone pattern of length \(k\), and a generalization
• On five types of crucial permutations with respect to monotone patterns
• \(S\)-crucial and bicrucial permutations with respect to squares
• Counting crucial permutations with respect to monotone patterns

This page was built for publication: Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q890954)