MathDB

The uniqueness conjecture for minimal superpermutations

A superpermutation on nn symbols is a string containing each of the n!n! permutations of those symbols as a contiguous substring; a minimal superpermutation is one of shortest possible length. Two superpermutations are related by relabelling when the same permutation of the symbols is applied throughout.

Uniqueness conjecture for minimal superpermutations. The minimal superpermutation on nn symbols is unique up to interchanging the roles of the symbols.

For n≤4n\leq 4, the source reports that the corresponding optimal solutions have been shown by brute force to be unique up to relabelling. The conjecture asks whether this uniqueness persists for arbitrary nn.

References

Primary source

Nathaniel Johnston, “Non-Uniqueness of Minimal Superpermutations”, arXiv:1303.4150 (2013).

combinatoricspermutationssuperpermutations

  • This was disproved years ago by Benjamin Chaffin, who computed all the minimal superpermutations for n=5n=5, and found that there are 8 of them up to relabelling.

    Robin Houston

  • I think the 6-symbol case is also resolved: we have long known many thousands of inequivalent examples of length-872 superpermutations on 6 symbols, and recent Lean-verified work shows that 872 is minimal for n=6.

    Robin Houston

Progress summary

Refreshed
Claimed solved

A verified five-symbol result shows that shortest strings are not unique, so the conjecture is false; the cases with six or more symbols are not fully classified.

The conjecture asserts that a shortest superpermutation is unique up to relabelling. Johnston’s 2013 construction exposed a conditional failure for n≥5n \ge 5, and Chaffin’s verification at n=5n=5 made the counterexample unconditional.

Known results

  • Minimality and uniqueness were established by brute force for n≤4n \le 4.
  • Johnston (2013) constructed multiple superpermutations of length ∑k=1nk!\sum_{k=1}^{n} k! for every n≥5n \ge 5; this was conditional on that length being minimal.
  • Chaffin (2014) verified that the minimum for n=5n=5 is 153153 and found exactly 88 minimal solutions up to the stated equivalence.
  • Houston (2014) exhibited length 872872 for n=6n=6, below the conjectured 873873, and extended the length counterexample to all n≥6n \ge 6.

August 2014 unconditional counterexample

Chaffin’s n=5n=5 computation proves that there are exactly 88 distinct minimal superpermutations, rather than a single relabelling class. Thus the uniqueness conjecture is definitively false, although the supplied sources do not settle uniqueness or enumerate all minima for n≥6n \ge 6.

Current status (as of August 2026): The conjecture is false, settled by n=5n=5; the number and structure of minimal superpermutations for n≥6n \ge 6 remain incompletely known.

Sources

Solutions 0

No solutions have been posted yet.