Non-Uniqueness of Minimal Superpermutations
Abstract:
We examine the open problem of finding the shortest string that contains each of the n! permutations of n symbols as contiguous substrings (i.e., the shortest superpermutation on n symbols). It has been conjectured that the shortest superpermutation has length \(\sum_{k=1}^n k!\) and that this string is unique up to relabelling of the symbols. We provide a construction of short superpermutations that shows that, if the conjectured minimal length is true, then uniqueness fails for all n ≥ 5. Furthermore, uniqueness fails spectacularly; we construct more than doubly-exponentially many distinct superpermutations of the conjectured minimal length.
Authors:
- Nathaniel Johnston
Download:
- Official publication from Discrete Mathematics
- Preprint from arXiv:1303.4150 [math.CO]
- Local preprint [pdf]
- Slideshow presentation [pdf]
Cite as:
- N. Johnston. Non-uniqueness of minimal superpermutations. Discrete Mathematics, 313:1553–1557, 2013.
Supplementary material:
- 96 small superpermutations – All 96 superpermutations on the symbols {1, 2, 3, 4, 5, 6} constructed via the method described in the paper.
- The minimal superpermutation problem – A blog post that introduces the problem considered in this paper.
- All minimal superpermutations on five symbols have been found – A blog post about some progress that Ben Chaffin made on the minimal superpermutation problem after this paper was written.
- “Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False – A blog post about a disproof to the minimal superpermutation conjecture, found by Robin Houston after this paper was written.