Skip to content

Research at St Andrews

S-crucial and bicrucial permutations with respect to squares

Research output: Contribution to journalArticle

Abstract

A permutation is square-free if it does not contain two consecutive factors of length two or more that are order-isomorphic. A permutation is bicrucial with respect to squares if it is square-free but any extension of it to the right or to the left by any element gives a permutation that is not square-free.

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 left-crucial (that is, not extendable to the left) square-free 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 right-crucial, left-crucial, and bicrucial permutations studied in the literature in various contexts, by introducing the notion of P-crucial permutations that can be extended to the notion of P-crucial words. In S-crucial permutations, a particular case of P-crucial permutations, we deal with permutations that avoid prohibitions, but whose extensions in any position contain a prohibition. We show that S-crucial 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 square-free permutations of length 19.
Close

Details

Original languageEnglish
Article number15.6.5
Number of pages22
JournalJournal of Integer Sequences
Volume18
Issue number6
StatePublished - 3 Jun 2015

    Research areas

  • Crucial permutation, Bicrucial permutation, Square, P-crucial permutation, S-crucial permutation

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Generating custom propagators for arbitrary constraints

    Gent, I. P., Jefferson, C., Linton, S., Miguel, I. & Nightingale, P. 1 Jun 2014 In : Artificial Intelligence. 211, 1, p. 1-33 33 p.

    Research output: Contribution to journalArticle

  2. Qualitative modelling via constraint programming

    Kelsey, T., Kotthoff, L., Jefferson, C. A., Linton, S. A., Miguel, I. J., Nightingale, P. & Gent, I. P. Apr 2014 In : Constraints. 19, 2, p. 163-173

    Research output: Contribution to journalArticle

  3. A review of literature on parallel constraint solving

    Gent, I. P., Miguel, I. J., Nightingale, P. W., McCreesh, C., Prosser, P., Moore, N. & Unsworth, C. Sep 2018 In : Theory and Practice of Logic Programming. 18, 5-6, p. 725-758 34 p.

    Research output: Contribution to journalArticle

  4. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P. 13 Jul 2018 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Complexity of n-Queens completion (extended abstract)

    Gent, I. P., Jefferson, C. A. & Nightingale, P. W. 13 Jul 2018 Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 5608-5611 4 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related by journal

  1. Equivalence classes of permutations under various relations generated by constrained transpositions

    Linton, S. A., Propp, J., Roby, T. & West, J. 2 Nov 2012 In : Journal of Integer Sequences. 15, 9, 23 p., 12.9.1

    Research output: Contribution to journalArticle

  2. Sequences realized by oligomorphic permutation groups

    Cameron, P. J. 1 Dec 2000 In : Journal of Integer Sequences. 3, 1

    Research output: Contribution to journalArticle

ID: 100937903