A useful symmetry

[Greg Egan]

This might be old news to people, but I haven’t seen it mentioned before.

For n=5, the Chaffin solutions, when drawn as 2-cycle graphs, consist of one isolated point and two isomorphic connected components with a very simple form: they are each just three vertices connected in a row. For one pair of Chaffin solutions, the isolated point and the roots of those two simple trees are the three 2-cycles in the first standard 3-cycle; the other solutions just involve a different choice of 3-cycle, so wlog we can focus on these particular ones.

There is a graph isomorphism of the entire 2-cycle graph that swaps the two non-trivial connected components of the Chaffin-solution subgraph and leaves the isolated point fixed.  If a 2-cycle is described as m|p when it has weight-2 edges from any permutation whose first digit is m and whose remaining n-1 digits are some rotation of p, then this symmetry operation is:

F_5(p) = exchange 1 and 3 in p, and reverse it

I recently noticed that there is a similar graph isomorphism for n=7.  If we define:

F_7(p) = exchange 1 and 2, and also 3 and 5 in p, and reverse it

then that preserves the incidence relations between 2-cycles.  It swaps the last two of the five 2-cycles in the first standard 3-cycle; it also swaps the first with the third, while leaving the second one fixed.

So, there is a potential for an n=7 solution to have this graph isomorphism F_7 as a symmetry, in the same way that F_5 is a symmetry for two of the Chaffin solutions.

I need to think more about the conceptual implications of this ... but on an immediate practical level, it might have the effect of speeding up some kinds of searches.  If we assume solutions with this symmetry, we can (slightly more than) halve the number of vertices being ruled in or out of a proposed 2-cycle graph, by essentially just building a single tree rooted at, say, the fifth standard 2-cycle, and then duplicating it using the action of F_7. In effect, rather than choosing single vertices, we choose orbits of vertices under the action of F_7 (and only use those orbits that contain two vertices; we don't include any fixed points of F_7, since they would join the two copies of the tree).

I’ve incorporated this symmetry into a search I’ve just started. It might not be enough to bring the degrees of freedom down to the point where a solution shows up in a reasonable time, but it seems like a worthwhile thing to try.

[Robin Houston]

Very nice observation. It’s news to me!

--
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/a4765638-0834-40df-9083-2145c60dd59c%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Robin Houston]

Can you explicitly show the two Chaffin superpermutations you’re considering, so I can make sure I’m looking at the same pair?

[Greg Egan]

As digit strings, they are:

1234512341523412534123541231452314253142351423154213524135214352134521

3542153421543215423124532145324153245132541325143251342513245312435124

3152431254312

and

1234512341523412534123541231452134251342153421354213452143521453214523

1425314235142315423124531243512431524312543215432514325413245132415324

1352413254312

which correspond to the 2-cycle subgraphs with vertices:

{{5,1,2,3,4},{1,2,4,5,3},{3,1,5,4,2},{4,1,3,2,5},{4,1,3,5,2},{5,1,4,2,3},{5,1,2,4,3}}

and

{{5,1,2,3,4},{1,2,5,4,3},{3,1,4,5,2},{5,1,3,2,4},{5,1,3,4,2},{5,1,4,2,3},{5,1,2,4,3}}

respectively.  The 2-cycles:

{{5,1,2,3,4},{5,1,4,2,3},{5,1,2,4,3}}

are the 2-cycles of the standard 3-cycle.  F_5 leaves the first of these fixed and exchanges the second and third.

[Niles Johnson]

More amazing progress -- thanks for letting us know!  I still try to think about arranging these graphs as the vertices and edges of a polytope, but so far I haven't come up with anything interesting.

--

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/8f05f130-814d-4996-8372-648110970974%40googlegroups.com.

[Greg Egan]

Using this twofold symmetry yields 2-cycle graphs for n=7 with 119 vertices in a matter of seconds ... but after running for another 24 hours there is no better result.

The twofold symmetry generalises to a tenfold symmetry, which can be used to build graphs with 5 disconnected isomorphic trees that each have a further twofold symmetry that leaves the root unchanged. In a few seconds, this approach yields graphs with 135 vertices, but then it’s impossible for the final target graph of 143 vertices to maintain the symmetry, and so far, adding 8 individual vertices to these highly symmetric forests doesn’t seem to be able to reach any higher – or at least not quickly!

[Greg Egan]

My search that assumed tenfold symmetry up to 135 vertices, and then added individual vertices freely, completed with no larger trees found, after checking about 52,600,000 tenfold-symmetric trees.  So at least that rules something out.

I’m also trying a version that relaxes this to fivefold symmetry, potentially up to 140 vertices, but so far that has only reached 125 vertices.

The search using twofold symmetry has remained at 119 vertices for two days.