question

[theReal_JamesGrime]

do the Superpermutations have to have a certain order or can the order be random e.g. n=9 abcdcabdc?

[Miles Gould]

Hi Marco!

(I'm assuming you're not the real James Grime...)

I'm not sure exactly what you mean by "a certain order". There are at least two things that can be ordered within a superpermutation:

• The symbols (for n=9, those would be {a, b, c, d, e, f, g, h, i} or {1, 2, 3, 4, 5, 6, 7, 8, 9} or whatever you please, it doesn't matter for the problem). We want those to appear in every order! A permutation can be thought of as an ordering of those symbols, so "abcdefghi" is a permutation, but so is "ghiadcbef". Note that "abcdcabdc" is not a permutation for n=9: it doesn't include all the symbols, and some of them appear more than once. A superpermutation is a string that contains every permutation as a substring, so it contains the symbols in every possible order. Let's take n=3 as an example, with symbols {a, b, c}. The possible permutations are abc, acb, bac, bca, cab and cba. The string "abcabacba" is a superpermutation for these symbols: you can check for yourself that it contains all the permutations.
• The permutations can appear in various orders within the superpermutation - for instance, in "abcabacba" we see abc, then bca, then cab, and so on. We can ask whether the permutations must appear in a particular order. If you just care about making any superpermutation, you can have them appear in any order - just write the permutations out in that order, and you've got a superpermutation. But if you want to find a minimal superpermutation (one that uses as few characters as possible), this question becomes more interesting. It turns out that for n=1, 2, 3, or 4, the order is fixed (up to relabelling of the symbols, which we don't care about) - there's essentially only one superpermutation in those cases. But for n=5, this is not the case! Ben Chaffin found eight essentially different minimal superpermutations on five symbols. For n=6 and higher, we don't yet know the answer, because we don't know for sure how long a minimal superpermutation must be. But it appears that the minimal superpermutations are not unique - we know of thousands of n=6 superpermutations of length 872 (our current best), and many n=7 superpermutations of length 5906 (again, our current best).

Hope that helps!

Miles

On Fri, 27 Aug 2021 at 03:44, theReal_JamesGrime <marco....@gmail.com> wrote:

do the Superpermutations have to have a certain order or can the order be random e.g. n=9 abcdcabdc?

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/86cdf14e-bb8f-40df-a98b-d94198f0cdb8n%40googlegroups.com.