Projects per year
Abstract
A permutation is squarefree if it does not contain two consecutive factors of length two or more that are orderisomorphic. A permutation is bicrucial with respect to squares if it is squarefree but any extension of it to the right or to the left by any element gives a permutation that is not squarefree.
Avgustinovich et al. studied bicrucial permutations with respect to squares, and they proved that there exist bicrucial permutations of lengths 8k+1, 8k+5, 8k+7 for k ≥ 1. It was left as open questions whether bicrucial permutations of even length, or such permutations of length 8k+3 exist. In this paper, we provide an encoding of orderings which allows us, using the constraint solver Minion, to show that bicrucial permutations of even length exist, and the smallest such permutations are of length 32. To show that 32 is the minimum length in question, we establish a result on leftcrucial (that is, not extendable to the left) squarefree permutations which begin with three elements in monotone order. Also, we show that bicrucial permutations of length 8k+3 exist for k = 2,3 and they do not exist for k =1.
Further, we generalize the notions of rightcrucial, leftcrucial, and bicrucial permutations studied in the literature in various contexts, by introducing the notion of Pcrucial permutations that can be extended to the notion of Pcrucial words. In Scrucial permutations, a particular case of Pcrucial permutations, we deal with permutations that avoid prohibitions, but whose extensions in any position contain a prohibition. We show that Scrucial permutations exist with respect to squares, and minimal such permutations are of length 17.
Finally, using our software, we generate relevant data showing, for example, that there are 162,190,472 bicrucial squarefree permutations of length 19.
Avgustinovich et al. studied bicrucial permutations with respect to squares, and they proved that there exist bicrucial permutations of lengths 8k+1, 8k+5, 8k+7 for k ≥ 1. It was left as open questions whether bicrucial permutations of even length, or such permutations of length 8k+3 exist. In this paper, we provide an encoding of orderings which allows us, using the constraint solver Minion, to show that bicrucial permutations of even length exist, and the smallest such permutations are of length 32. To show that 32 is the minimum length in question, we establish a result on leftcrucial (that is, not extendable to the left) squarefree permutations which begin with three elements in monotone order. Also, we show that bicrucial permutations of length 8k+3 exist for k = 2,3 and they do not exist for k =1.
Further, we generalize the notions of rightcrucial, leftcrucial, and bicrucial permutations studied in the literature in various contexts, by introducing the notion of Pcrucial permutations that can be extended to the notion of Pcrucial words. In Scrucial permutations, a particular case of Pcrucial permutations, we deal with permutations that avoid prohibitions, but whose extensions in any position contain a prohibition. We show that Scrucial permutations exist with respect to squares, and minimal such permutations are of length 17.
Finally, using our software, we generate relevant data showing, for example, that there are 162,190,472 bicrucial squarefree permutations of length 19.
Original language  English 

Article number  15.6.5 
Number of pages  22 
Journal  Journal of Integer Sequences 
Volume  18 
Issue number  6 
Publication status  Published  3 Jun 2015 
Keywords
 Crucial permutation
 Bicrucial permutation
 Square
 Pcrucial permutation
 Scrucial permutation
Fingerprint
Dive into the research topics of 'Scrucial and bicrucial permutations with respect to squares'. Together they form a unique fingerprint.Projects
 2 Finished

A Constraint Solver Synthesiser: A Constraint Solver Synthesiser
Miguel, I. J., Balasubramaniam, D., Gent, I. P., Kelsey, T. & Linton, S. A.
1/10/09 → 30/09/14
Project: Standard

HPCGAP: High performance computational: HPCGAP High Performance Computational Algebra and Discrete Mathematics
Linton, S. A., Gent, I. P. & Hammond, K.
1/09/09 → 28/02/14
Project: Standard