[r-t] Bobs only Stedman Triples
Mark Davies
mark at snowtiger.net
Thu Oct 12 15:10:14 UTC 2017
OK I have discovered this fascinating paper, co-authored by Andrew Johnson:
"Change Ringing and Hamiltonian Cycles : The Search for Erin and
Stedman Triples"
https://arxiv.org/pdf/1702.02623.pdf
Reading this has practically knocked me out. First of all, it's pretty
easy to digest - the maths and graph/group theory isn't heavy. But if
I'm reading it right, there are some astounding results here. In
particular (again, contingent on me having understood it correctly) the
table on page 11 appears to show that Andrew has proved these statements:
1. A bobs-only peal of Erin Triples must be a one-part, or an exact
two-part. No higher part structures are possible.
2. There are no 7-part bobs-only peal of Stedman Triples.
3. Bobs-only 5-, 6-, 10- and 20- parts peals of Stedman Triples exist,
and Andrew has enumerated all of them.
But maybe I have this wrong - where are the peals in category (3) - why
hasn't Andrew published them? And the paper shows that Andrew had not
yet discovered whether an exact 3-part was possible; but perhaps it was
published before he did.
The main technical advance that Andrew describes is a way of applying
recent very powerful "heuristic" Travelling Salesman Problem (TSP)
and/or Hamiltonian Cycle Problem (HCP) algorithms to the search for
bobs-only peals. The paper clearly and neatly explains how he has done
this, using "in/out subgraphs" to apply the constraints of the methods
to a general graph suitable for input to an HCP solver. It's a masterpiece.
Given that research on these algorithms is proceeding apace, and
computer time for searches gets ever cheaper, Andrew is almost certainly
right to claim that the bobs-only Erin problem won't hold out for much
longer ("the continued evolution of HCP heuristics and parallel
computing technology should make finding a HC in Erin1, and hence a
bobs-only peal of Erin Triples, a more tractable problem"). Now that is
exciting.
The other fascinating part of the paper (for me) is Andrew's discovery
that Stedman Triples provides "very difficult" HC problems. He describes
a competition for solving HCPs, during which only the HCs based on
Stedman remained unsolved:
"In the FHCP Challenge, which ran for one year, a set of 1001 graphs
known to be Hamiltonian needed to be solved. The first team to solve the
graphs would win the prize of $1001US, and if no teams were successful
after a year, the team with the most correctly solved graphs would win.
At the conclusion of the FHCP Challenge, only 16 of the graphs remained
unsolved by any of the submissions, all of which were based on the
(Hamiltonian) Stedman graphs."
Wow, just wow.
MBD
More information about the ringing-theory
mailing list