The lengths for which bicrucial square-free permutations exist

DOI10.54550/ECA2022V2S4PP4MaRDI QIDQ6156001zbMATH OpenOpenAlexFDO

Authors Carla Groenland, Tom Johnston

Publication date 9 June 2023

Published in Enumerative Combinatorics and Applications (Search for Journal in Brave)

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

zbMATH Keywords

bicrucialpermutation patternsquare-free

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: A square is a factor $S=(S_1;S_2)$ where $S_1$ and $S_2$ have the same pattern, and a permutation is said to be square-free if it contains no non-trivial squares. The permutation is further said to be bicrucial if every extension to the left or right contains a square. We completely classify for which $n$ there exists a bicrucial square-free permutation of length $n$.

Recommendations

• \(S\)-crucial and bicrucial permutations with respect to squares
• Crucial and bicrucial permutations with respect to arithmetic monotone patterns
• Pattern avoidance in permutations and their squares
• Unshuffling permutations
• Algorithmic and algebraic aspects of unshuffling permutations

Cites work

• \(S\)-crucial and bicrucial permutations with respect to squares
• Annihilators in Nonrepetitive Semigroups
• Avoidable patterns in strings of symbols
• Extremal square-free words
• Lengths of extremal square-free ternary words
• On square-free permutations

Cited in

(5)

• On five types of crucial permutations with respect to monotone patterns
• \(S\)-crucial and bicrucial permutations with respect to squares
• Bicrucial k-power-free permutations
• On P-crucial and S-crucial square-free permutations
• Crucial and bicrucial permutations with respect to arithmetic monotone patterns

This page was built for publication: The lengths for which bicrucial square-free permutations exist

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