On P-crucial square-free permutations

2025/08/09 by Valyuzhenich, Alexandr
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.06907

Abstract

A permutation is square-free if it does not contain two consecutive factors of length two or more that are order-isomorphic. A square-free permutation of length n is P-crucial, where P is a subset of \0,1,…,n\, if any of its extensions in any position from the set P contains a square. In 2015, Gent, Kitaev, Konovalov, Linton and Nightingale initiated the study of P-crucial square-free permutations. In particular, they showed that \0,1,n-1,n\-crucial square-free permutations of length n, where n≤ 22, exist if and only if n=17 or n=21. In this work, we prove that for any m≥ 2 there exists a \0,1,8m+4,8m+5\-crucial square-free permutation of length 8m+5.

Citations

• Bicrucial k-power-free permutations
• Counting crucial permutations with respect to monotone patterns
• On five types of crucial permutations with respect to monotone patterns
• Variations on twins in permutations
• S-crucial and bicrucial permutations with respect to squares
• Crucial and bicrucial permutations with respect to arithmetic monotone patterns

Related

• S-crucial and bicrucial permutations with respect to squares
• On five types of crucial permutations with respect to monotone patterns
• Bicrucial k-power-free permutations
• Counting crucial permutations with respect to monotone patterns
• Pattern avoidance in permutations and their squares