[r-t] Bobs only Stedman Triples

[Andrew Johnson]

> From: Mark Davies <mark at snowtiger.net>
> OK I have discovered this fascinating paper, co-authored by Andrew 
Johnson:
> 
> "Change Ringing and Hamiltonian Cycles : The Search for Erin and
> Stedman Triples"
> 
by Michael Haythorpe and Andrew Johnson
https://arxiv.org/abs/1702.02623
> 
> 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.
This is for an exact N-part, not necessarily for irregular N-parts.

The paper was looking at whether there were Hamiltonian cycles in the 
graph reduced by a group.
A Hamiltonian cycle can be useful when then applied to the full graph; 
either directly given the appropriate part-end for an exact N-part, or 
giving an odd number of round blocks, possibly linkable using Q sets of 
bobs or omits.

It didn't consider subcycles covering the reduced graph e.g. my 10-part 
Stedman peal where there is one cycle covering most of graph which expands 
to 5 2-part blocks, and another cycle which expands to 2 5-part blocks 
(the B-blocks with 76 behind).

The paper also didn't cover mixed parity groups such as 5.03 (Thurstans' 
20 part-ends)
http://ringing.org/peals/triples/erin/#1854
which does have a Hamiltonian cycle in the reduced graph, but having 
out-of-course group elements must generate an even number of round blocks 
in the full graph.
> 
> 2. There are no 7-part bobs-only peal of Stedman Triples.
There are no exact 7-parts of Stedman Triples. I did consider subcycles, 
but I can't see a simple or complicated linkage for the multiple blocks.
> 
> 3. Bobs-only 5-, 6-, 10- and 20- parts peals of Stedman Triples exist, 
> and Andrew has enumerated all of them.
These are Hamiltonian cycles in the reduced group graph, but they aren't 
actually peals. They don't directly lead to peals. There is no Hamiltonian 
cycles in 20-part graph (group 7.12) giving 5 4-part round blocks - 
instead they are 4 5-part blocks. The 10-part blocks are those which link 
into 5 2-part blocks but don't have the Q sets for a bobs-only peal.
http://www.ringing.org/peals/triples/stedman/#1741
I haven't published the 6-part blocks, but they are of the form 2 3-part 
blocks or 6 1-part blocks instead of 3 2-part blocks. The only 5-part 
blocks are just the 10-part blocks, so there isn't an exact 5-part peal.
> 
> 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 paper was submitted before I discovered my 3-parts.
> 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.
I don't know - a direct 1-part search is still impossibly large.
> 
> 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
> 

--
Andrew Johnson








Unless stated otherwise above:
IBM United Kingdom Limited - Registered in England and Wales with number 
741598. 
Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU