[r-t] Bobs only Stedman Triples

[Mark Davies]

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