Superpermutations but with Repeated Permutations Allowed

[Cole Fritsch]

I have two side-problems related to superpermutations. Proofs for these problems may be able to reduce the search-space slightly and may allow some mathematical clarity:

One of the conditions of superpermutations is that all permutations must be included no more than once. I have always found this condition strange because it has no obvious change to the problem and its solutions. I believe that minimal superpermutation without a restriction on permutation repetitions may be the same as normal minimal superpermutations. I have not found any information related to this question yet. I believe that Egan's upper bound and the 4chan lower bound hold for this problem. I believe Zach Hunter's lower bound is dependent on repetition not being allowed, but it may be possible to prove that it still holds for this case.

Another similar question asks if n-length strings that feature repeated symbols (permutations with repetition) featured in minimal superpermutations are never repeated. Needless to say, it is unlikely that a minimal superpermutation would feature this form of repetition, because it is quite restrictive. From what I have found, a repeated permutation with repetition can only exist in an edge of 3 or greater. The only pair of 3-edges that can feature the same permutation with repetition are 123...xyz --> 456...xyz231 3-edges.

If anyone has any idea on these problems, I am very interested to hear about it.

-Cole Fritsch

[Zach Hunter]

Just for clarification, repetition of permutations is allowed in my approach. It is for this reason that I define the graph in the way I do, and do not restrict my self to having just one 2-edge. (instead, I have both tau and sigma^2)

[Miles Gould]

On Mon, 6 Jan 2020 at 22:38, Cole Fritsch <colefri...@gmail.com> wrote:

One of the conditions of superpermutations is that all permutations must be included no more than once.

I was surprised to see that Greg Egan includes this in his definition of superpermutation (at http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html) - I'd always thought the natural definition was "every permutation appears at least once", and it was an open question as to whether there existed minimal superpermutations which visited some permutation more than once. We've certainly discussed it as an open problem before, eg in the thread following https://groups.google.com/d/msg/superpermutators/-c7ZoXcc05M/4t_2FN9MAAAJ.

I have always found this condition strange because it has no obvious change to the problem and its solutions.

It means that superpermutations coincide with Hamiltonian tours of the permutation graph, which allows us to use established machinery from graph theory (such as Aaron Williams' work). But yes, it's not obvious how (or whether!) this restriction changes the solutions.

 

I believe that minimal superpermutation without a restriction on permutation repetitions may be the same as normal minimal superpermutations.

Yes, I think most of us believe that too, but we can't prove it yet :'(

 

I have not found any information related to this question yet. I believe that Egan's upper bound and the 4chan lower bound hold for this problem. I believe Zach Hunter's lower bound is dependent on repetition not being allowed, but it may be possible to prove that it still holds for this case.

An upper bound on the length of a minimal exactly-once superpermutation also gives us an upper bound on the length of a minimal at-least-once superpermutation (suppose m1 is the length of a minimal at-least-once SP, and m2 is the length of a minimal exactly-once SP: we must have m2 >= m1 since every =1 SP is also a >=1 SP, so if U is an upper bound on m2 then U >= m2 >= m1 and U is an upper bound on m1 as well). From a quick scan of https://oeis.org/A180632/a180632.pdf, the (careful version of the) 4chan proof does not assume each permutation is visited exactly once - Houston, Pantone and Vatter are careful to note that their superpermutations do not necessarily correspond to Hamiltonian tours.

Another similar question asks if n-length strings that feature repeated symbols (permutations with repetition) featured in minimal superpermutations are never repeated. Needless to say, it is unlikely that a minimal superpermutation would feature this form of repetition, because it is quite restrictive. From what I have found, a repeated permutation with repetition can only exist in an edge of 3 or greater. The only pair of 3-edges that can feature the same permutation with repetition are 123...xyz --> 456...xyz231 3-edges.

I don't know of any work along these lines, but as you say it sounds quite unlikely. Perhaps worth looking into, though!

HTH,

Miles

[Robin Houston]

I think this is a mistake in Greg’s definition, or at any rate a non-standard inequivalent definition. It’s true that none of the minimal superpermutations we know about have repeated permutations, but we don’t have any proof that they mustn’t.

When relating superpermutations to paths in a graph, my own preferred approach is to allow “non-primitive” edges in the graph, such as the weight-3 edge 123X → X132 (which is “non-primitive” since it can be decomposed into a longer path 123X → 23X1 → X132 with the same total weight), and to look at Hamiltonian paths in the graph. There is not a one-one correspondence between superpermutations and Hamiltonian paths in this graph, but there is a two-way translation that does not increase the weight which means that minimal superpermutations and minimum-weight Hamiltonian paths have the same weight.

Another possible approach is the one used in the paper with Pantone and Vatter, where non-standard edges are excluded but nodes may be visited more than once.

Best wishes,

Robin

--
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/CAKFNCm0chgcWSKWs5RQb2qkHEjNzzwPNSbS1BRzeP8fum5n%3Dzw%40mail.gmail.com.

[Cole Fritsch]

I am sorry about that, Zach Hunter. I should have known since I read it already. I did not know why you set it up that way till just now and that would explain why you wanted the 3! 3-edges. I misunderstood it since I am still under my own understanding of your concept where I used this restriction. I just jumped to the assumption that it would be a direct conflict with the no repetition part of the problem, but it should make no difference for a lower bound since it is a removed restriction. 

As you probably already know, increasing the size of your path that is repeated in order to improve the bound can get quite unpredictable. The availability of a path to repeat segments of its permutations to construct a optimal path is just another thing to keep track of, so it is probably best to not allow repetition for the sake of simplicity for more difficult bounds. This is just one example of the complexity of this side-problem.

On Tue, 7 Jan 2020 at 13:04, Miles Gould <mi...@assyrian.org.uk> wrote:

An upper bound on the length of a minimal exactly-once superpermutation also gives us an upper bound on the length of a minimal at-least-once superpermutation (suppose m1 is the length of a minimal at-least-once SP, and m2 is the length of a minimal exactly-once SP: we must have m2 >= m1 since every =1 SP is also a >=1 SP, so if U is an upper bound on m2 then U >= m2 >= m1 and U is an upper bound on m1 as well). From a quick scan of https://oeis.org/A180632/a180632.pdf, the (careful version of the) 4chan proof does not assume each permutation is visited exactly once - Houston, Pantone and Vatter are careful to note that their superpermutations do not necessarily correspond to Hamiltonian tours.

As for the 4chan lower bound, I really should have said that one can change very few aspects of the proof to fit this question and it will still hold. From what I have seen, the "Proof" part of the graph makes no mention of this restriction. Of course, I only did a really quick check. As for the upper bound, I meant to imply the same logic as you mentioned.

The purpose of these questions is to get rid of some little annoyances with making graphs for proofs or making a program to find superpermutations. As I mentioned before, proving the first conjecture will allow algorithms to run through superpermutations much faster for this side-problem (which I guess is the real problem). The second side-problem is much simpler and there are ways to avoid defining a graph around this, but it is still a minor annoyance. 

-Cole Fritsch

--
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 superpermutators+unsubscribe@googlegroups.com.

[Greg Egan]

I've changed the definition on the web page, from "exactly once" to "at least once".

At the time I wrote the page that seemed more elegant, and more appropriate: just as a permutation contains every symbol in some set S exactly once, a superpermutation "should" contain every permutation of S exactly once. But since most other people are using a different definition, and since we still haven't been able to prove what everyone believes (that no minimal superpermutation will contain a repetition), I'll go with the consensus.

> To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq2Bj289-X-6XOaYmkGTW3WC5-HzKtom%2BN5JyY0QOK%2BwzQ%40mail.gmail.com.