Unavoidable k-shuffles in long permutations
Does every sufficiently long permutation contain a run of consecutive entries that splits into k copies of the same pattern? Known thresholds: n0(2) = 6, n0(3) = 12.
Cite
@misc{cairn-k-shuffle-factors-permutations,
title = {Unavoidable k-shuffles in long permutations},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/k-shuffle-factors-permutations}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/k-shuffle-factors-permutations)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
A permutation of length k·p is a k-shuffle of a pattern τ of length p if its entries can be split into k subsequences, each order-isomorphic to τ. A factor of a permutation is a block of consecutive entries. Conjecture: for each k there is n_0(k) such that every permutation of length n > n_0(k) has a factor of length ≥ 2k that is a k-shuffle (of some pattern). A related form (Bevan, Elvey Price, Felsner): every sufficiently long permutation has a factor that is a k-shuffle of 12 or of 21.
What is known
The report lists n_0(2) = 6, n_0(3) = 12 and n_0(4) ≤ 26; computer checks confirm the 12/21 form for small k, and partial structural results are known.
What counts as progress
- The exact value of n_0(4), then bounds for n_0(5), n_0(6), with an explicit longest avoiding permutation and an exhaustive or SAT proof that nothing longer avoids.
- A conjectured formula for n_0(k) supported by the data, and a proof for all k.
How it is checked
An avoiding permutation is checkable directly; the exhaustion step ships solver proofs or search code and logs (level B).
Source. Posed by Mathilde Bouvel in the open problem session of the Oberwolfach workshop Mini-Workshop: Permutation Patterns (2024), recorded in Oberwolfach Reports 6/2024, p. 287 (EMS Press, DOI 10.4171/OWR/2024/6), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.