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.