Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples

Michael Haythorpe, Andrew Johnson

Abstract


A very old problem in campanology is the search for peals. The latter can be thought of as a heavily constrained sequence of all possible permutations of a given size, where the exact nature of the constraints depends on which method of ringing is desired. In particular, we consider the methods of bobs-only Stedman Triples and Erin Triples; the existence of the latter is still an open problem. We show that this problem can be viewed as a similarly constrained (but not previously considered) form of the Hamiltonian cycle problem (HCP). Through the use of special subgraphs, we convert this to a standard instance of HCP. The original problem can be partitioned into smaller instances, and so we use this technique to produce smaller instances of HCP as well. We note that the instances known to have solutions provide exceptionally difficult instances of HCP.

Keywords


change ringing, triples, Stedman, Erin, Hamiltonian cycles

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.5

References

D.L. Applegate, R.B. Bixby, V. Chava ́tal and W.J. Cook. Concorde TSP Solver: http://www.tsp.gatech.edu/concorde/index.html, (2015), accessed October 12th 2016.

P. Baniasadi, V. Ejov, J.A. Filar, M. Haythorpe and S. Rossomakhine. Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Math. Program. Comput. 6 (1) (2014), 55-75.

A. Chalaturnyk. A Fast Algorithm For Finding Hamiltonian Cycles. Ph.D Thesis, University of Manitoba (2008).

V. Ejov, M. Haythorpe and S. Rossomakhine. A linear-size conversion of HCP to 3HCP. Austral. J. Combin. 62 (1) (2015), 45–58.

D. Eppstein. The traveling salesman problem for cubic graphs. In Frank Dehne, Jo ̈rg-Ru ̈diger Sack, and Michiel Smid, editors, Algorithms and Data Struct., volume 2748 of Lecture Notes in Computer Science, pages 307–318. Springer Berlin (2003).

D. Glynn, M. Haythorpe and A. Moeini. Directed in-out graphs of optimal size. Austral. J. Combin. 72 (2) (2018), 405–420.

M. Haythorpe. FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem. Bull. ICA 83 (2018), 98–107.

M. Haythorpe. Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles. Electron. J. Graph Theory Appl. 4 (1) (2016), 18–25.

K. Helsgaun. An effective implementation of Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000), 106–130.

A. Johnson. Bobs-only Stedman Triples made easy. http://myweb.tiscali.co.uk/saddleton/stedman/10part.html, (1995).

A. Johnson and P.A.B. Saddleton. Peals of Stedman Triples with bobs only. http://myweb.tiscali.co.uk/saddleton/stedman/ajart.htm, (1995).

R.M. Karp. Reducibility among Combinatorial Problems, Springer, New York, (1972).

C.H. Papadimitriou and K. Steiglitz. Some examples of difficult traveling salesman problems, Oper. Res. 26 (3) (1978), 434-443.

B.D. Price. Mathematical groups in campanology. The Math. Gazette 53 (384) (1969), 129–133.

B.D. Price. The Composition of Peals in Parts. http://www.ringing.info/bdp/peals-in-pats/parts-0.html, accessed October 12th 2016.

R.A. Rankin. A campanological problem in group theory. Proc. Cambridge Philos. Soc. 44 (1948), 17–25.

R.A. Rankin. A campanological problem in group theory II. Proc. Cambridge Philos. Soc. 62 (1966), 11–18.

R.G. Swan. A simple proof of Rankin’s campanological theorem. Am. Math. Mon. 106 (2) (1999), 159–161.

W.H. Thompson. A Note on Grandsire Triples, 1886, reprinted in Grandsire, JW Snowdon, London, (1905).

A.T. White. Ringing the cosets. Am. Math. Mon. 94 (8) (1987), 721–746.

A.T. White. Ringing the cosets II. Math. Proc. Cambridge 105 (1) (1989), 53–65.

C.J.E. Wyld. A 250-year-old problem solved. The Ringing World, p.197, (1995).


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats