Non-uniqueness of minimal superpermutations

DOI10.1016/J.DISC.2013.03.024MaRDI QIDQ389216zbMATH OpenOpenAlexWikidataFDO

Authors Nathaniel Johnston

Publication date 20 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.4150

zbMATH Keywords

permutationshortest superstringsuperpermutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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 $su{m}_{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.

Recommendations

• scientific article; zbMATH DE number 617582
• Skip letters for short supersequence of all permutations
• Shorter strings containing all \(k\)-element permutations
• Containing all permutations
• Shortest prefix strings containing all subset permutations

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 617582 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• On finding minimal length superstrings
• The greedy algorithm for shortest superstrings

Cited in

(6)

• Shortest prefix strings containing all subset permutations
• Preprocessing of propagation redundant clauses
• Containing all permutations
• Skip letters for short supersequence of all permutations
• Supertrees
• Shorter strings containing all \(k\)-element permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Non-uniqueness of minimal superpermutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q389216)