Superpermutation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring.

It has been shown that for 1 ≤ n ≤ 5, the smallest superpermutation on n symbols has length 1! + 2! + … + n! (sequence A180632 in the OEIS). The first five superpermutations have respective lengths 1, 3, 9, 33, and 153, forming the strings 1, 121, 123121321, 123412314231243121342132413214321, and the string:

123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321

Lower and upper bounds[edit]

Lower bound[edit]

In September 2011, an anonymous poster of the internet imageboard 4chan proved that the smallest superpermutation on n symbols (n ≥ 2) has at least length n! + (n−1)! + (n−2)! + n − 3.[1] The proof for this lower bound came to the general public interest in October 2018, after mathematician and computer scientist Robin Houston tweeted about it.[2][3] On 25 October 2018, Robin Houston, Jay Pantone, and Vince Vatter posted a refined version of this proof in OEIS.[4]

Upper bound[edit]

On 20 October 2018, by adapting a construction by Aaron Williams for constructing Hamiltonian paths through the Cayley graph of the symmetric group,[5] Greg Egan devised an algorithm to produce superpermutations of length n! + (n−1)! + (n−2)! + (n−3)! + n − 3.[6] Up to 2018, these are the smallest superpermutations known for n ≥ 7.

See also[edit]

Further reading[edit]

  • Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construction of small superpermutations and minimal injective superstrings", Congressus Numerantium, 93: 91–98, Zbl 0801.05004
  • Johnston, Nathaniel (July 28, 2013), "Non-uniqueness of minimal superpermutations", Discrete Mathematics, 313 (14): 1553–1557, arXiv:1303.4150, doi:10.1016/j.disc.2013.03.024, Zbl 1368.05004, retrieved March 16, 2014
  • Houston, Robin (21 August 2014), "Tackling the Minimal Superpermutation Problem", arXiv:1408.5108 [math.CO]

References[edit]

  1. ^ Anonymous (17 September 2011). "Permutations Thread III". Warosu, a 4chan archive. Retrieved 27 October 2018.
  2. ^ Griggs, Mary Beth. "An anonymous 4chan post could help solve a 25-year-old math mystery". The Verge.
  3. ^ Houston, Robin. "A curious situation. The best known lower bound... (1054637891085918209)". Twitter. Retrieved 27 October 2018.
  4. ^ Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (October 25, 2018). "A lower bound on the length of the shortest superpattern" (PDF). OEIS. Retrieved 27 October 2018.
  5. ^ Aaron, Williams. "Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)". arXiv:1307.2549v3.
  6. ^ Egan, Greg (20 October 2018). "Superpermutations". Retrieved 27 October 2018.

External links[edit]