Current open problems, aka "how can I help?"

[Miles Gould]

Hi everyone,

Greg's page at http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html already serves as a good orientation guide to the current state of the mathematics, but it occurred to me that it might be useful for newcomers to have a list of our current open problems and lines of attack, so they can better dive in. This should probably be a living document (do we need a wiki or something?), but I thought I'd bash out an attempt here as a starting point for discussion.

If you are a mathematician

• Can the lower bound be improved? See the thread at https://groups.google.com/forum/?#!topic/superpermutators/RQCZI4OALdM
• Can the Egan-Williams upper bound be improved?
• Is there some way of classifying the existing solutions for n in {5, 6, 7}?
• Can we speed up Coanda's backtracking search any more, perhaps by taking greater advantage of the symmetries of the permutation graph?
• Can you make any progress on related problems? https://arxiv.org/abs/1810.08252 lists some.
• Is there some other helpful idea that we're missing? Relevant fields here are combinatorics, graph theory, and group theory, but for all I know the next breakthrough will come from a hidden connection to knot theory or noncommutative geometry or magnetohydrodynamics or something.

If you are a computer scientist

• Why do TSP solvers struggle with permutation graphs when they can handle much larger graphs in general?
• Is there some way to mutate permutation graphs to make them more TSP-friendly?
• Are there nonstandard TSP-solver algorithms that are more suited to permutation graphs?
• Is there some other search algorithm that would work better than our current ones?
• Is there some other helpful idea that we're missing?

If you are a programmer

• Can the distributed Chaffin search client be made more efficient? (needs: C)
  
• Can the distributed Chaffin search server be improved to handle more concurrent clients? (needs: PHP or SQL or concurrent programming theory)
• (once the server can handle the load) How can we provide client binaries for easy download, especially on Windows?
• Can any of the other search programs be sped up? (needs: C)
• Can you think of a better search algorithm than the ones we've tried?
  

What have I missed?

Miles

[Miles Gould]

*clicks "Send"*

*realises the obvious thing I missed*

If you have access to a computer

Download, compile and run the distributed Chaffin search client!

Miles

[Miles Gould]

I thought of two more for mathematicians:

 - Can you prove that a minimal superpermutation never visits any permutation twice?

 - Can you prove that some edges (e.g. edges of maximum weight) are not needed for minimality?

Miles

[B Metz]

Have any minimal values been found to date that do visit a permutation more than once?  For example, I checked all of the 872 files in the superpermutations/6/872 folder without finding one.  

As a side note, it was interesting to look at some bulk stats by processing splitsuperperm.py output for each.  For example, across the 1685 values, every one consisted of 145 clusters of valid permutation values and exactly 147 waste values, i.e. only two back-to-back invalid value instances.  Each of the valid value clusters contained 2, 3, 4 or 6 permutation values but never 1 or 5.  The median occurrence of those four counts were 17, 16, 16 & 95, respectively; however, each could be as low as 13, 8, 11 & 95 or as high as 23, 24, 21 & 98, though obviously not all at the same time.  I don't think this is significant and may simply hint at the algorithm used to create the 872 files; however, plotting the count of values vs. position in the superperm string produced a graph not unlike something you might see in gnu radio.  Here's an example

File 1 2 3 4 5 6 valid_count 1 2 3 4 1/872.158da2f.txt 0 19 12 19 0 95 145 6 6 6 6 1/872.424e8a1.txt 0 19 12 19 0 95 145 6 6 6 4 1/872.5e9adb3.txt 0 19 12 19 0 95 145 6 6 6 6 1/872.d006594.txt 0 19 12 19 0 95 145 6 6 6 6 872.0053cad.txt 0 18 14 18 0 95 145 2 2 6 6 872.008c387.txt 0 20 10 20 0 95 145 6 6 6 6
In case it pique's anyone interest, I've shared the excel file and the two rudimentary bash scripts used to create the data points.  They may go on my GitHub repo for this stuff later, but I didn't want to include them there and they're being run out of a local copy of the superperm repo anyway. https://drive.google.com/drive/folders/1NJPsatdDXAG-nuBSCtL5HczL-bwRTZYv

--
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 post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAKFNCm2NJXhkm3ZXT3Zes06WSFZq4iO_5_2AU%3D3FKH66xYH4Fg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Greg Egan]

> On 17 May 2019, at 3:45 pm, B Metz <bwm...@gmail.com> wrote:
>
> Have any minimal values been found to date that do visit a permutation more than once? For example, I checked all of the 872 files in the superpermutations/6/872 folder without finding one.
>

No, there are none.

[Miles Gould]

I guess this question can be split into two:

1. Are there any minimal superpermutations which visit a permutation more than once?
2. Are there any n for which all minimal superpermutations visit some permutation more than once?

A "no" answer to 1 implies a "no" answer to 2, but the converse doesn't hold. We would like the answer to 2 to be "no" so we can exclude paths with loops from our searches and proofs; it seems very likely that the answer to 2 is indeed "no", but we don't have a proof of that.

Miles

[Ken Helberg]

 I hadn't looked at the results for n=6, but earlier this week I noticed that all the minimum strings for n=5 do not have clusters of valid permutations of 1 or 4. I had wondered if some of the checks could be culled based on this (back out of sequences where the next character would result in a waste character if the number of sequential valid permutations is n-1 or 1), but I worried this would just be conjecture and lead to incorrect results.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Miles Gould]

There's some previous work on the lengths of spans-of-permutations at https://docs.google.com/document/d/1ufq91EAHr02P3dNqDsXGKQph0yTupd3Fpdx1Tv1sK48/edit, but I don't think it directly bears on this question of culling the search.

Miles

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAKFNCm2NJXhkm3ZXT3Zes06WSFZq4iO_5_2AU%3D3FKH66xYH4Fg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

--

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 post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/a7ee3bf4-0097-47d9-8e0d-cbec31df4886%40googlegroups.com.

[Benjamin Chaffin]

Nathaniel Johnston made similar observations around the time of his original blog post, and suggested some constraints on what a minimal superpermutation might look like for N=6. I'll just quote his original email:

=====

- Never place more than 2 blanks next to each other

- Never have blanks that are separated by exactly 1 or 5 non-blanks (e.g., never have a string containing something like a2c or a23456b, but strings like a23a are OK)

- Start the superpermutation with:  12345612345a623451b634512c645123d651234ae623415b634152c641523d615234a

I realize that these restrictions don't reduce the search space *too* much, but does it get things into the "maybe possible" region? The above restrictions are sort of best guesses that I have for what a minimal superpermutation would look like when N = 6, based on the 6 "weird" superpermutations you found in the N = 5 case.

=====

I spent a while running with these constraints, but although they trim the search space somewhat it wasn't nearly enough to achieve a full solution on a single machine. (Seeing how many clients are contributing the the distributed search makes it clear just how far out of reach that was!) And of course they are only guesses to maybe help find a solution faster -- a search with these constraints might find a new shortest string, but would not prove the minimum.

  ben

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAKFNCm2Frr9sz0OP5NJtOw2pwnHSEvvkZKKQANsmGfpXrBUY%3Dg%40mail.gmail.com.