810 new length-872 superpermutations on 6 symbols

[Robin Houston]

Hello!

I’m very slowly starting to understand something about the range of ways short superpermutations can behave. I’ve been discussing it with Vince and Jay a bit. I think I’ll be able to show a slightly improved lower bound once I’ve put it all together, but the strong bound n! + (n-1)! + (n-2)! + (n-3)! + (n-4) is out of reach at the moment – and I’m not at all sure it is really true.

Anyway, I’ve found a new class of length-872 superpermutations on 6 symbols. There are 774 of them. You can download a gzipped text file from https://github.com/superpermutators/superperm/blob/master/superpermutations/6/872-treelike-slack1.txt.gz

These superpermutations consist of two 3-cycles joined by an edge of weight 4, with the rest of the 2-cycles attached as a tree. So they visit fewer 2-cycles than the 42,288 we had before, but this is counteracted by the edge of weight 4 and so the total length is the same.

There are also 36 length-872 superpermutations that consist of three 3-cycles connected by weight-4 edges, which I’ve put at https://github.com/superpermutators/superperm/blob/master/superpermutations/6/872-treelike-slack2.txt

I found them using the same exact cover algorithm as last time. Code is in https://github.com/superpermutators/superperm/blob/master/bin/xc2.py (It’s configured to find the ones with two 3-cycles, but you can change that by commenting out line 277 and uncommenting line 278.)

Best wishes,

Robin

[Robin Houston]

One thing it would be interesting to look at, which I haven’t had a chance to look at yet:

Does the pattern “a complete 4-cycle, with the rest of the 2-cycles attached as a tree” generalise nicely to higher n?

If so, that will improve the Egan upper bound by one.

R

[Greg Egan]

That would be amazing!  For anyone who hasn't seen them, these structures (for n=6) are incredibly simple.  Apart from 9 2-cycles that do not intersect with each other at all, they consist of three trees:

[Justin Hoffman]

Could you or someone modify the code to also output for each edge-weight how many times it was traversed?

I would do it myself, but I'm not familiar with the algorithm nor Python, so I'm sure I would get something wrong in the reverse engineering.