Series

Hamiltonian cycles — the series

8 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

    A walk that changes one thing at a time

    Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

    part 1 · discrete
  2. The 1,344 tours of the 4-cube, by how often each place changes. A bar for each pattern of change counts among all closed walks through the 4-cube, with the number of tours having it; the reflected code's pattern and the perfectly even one are marked.

    Every place changes back

    A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.

    part 2 · discrete
  3. A cycle through the middle two levels of the 5-cube: 20 words. The words of length 5 with 2 or 3 ones placed round a ring in the order of a Hamiltonian cycle, alternating between the two levels, each step changing a single place.

    The walk through the middle levels

    On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.

    part 3 · discrete
  4. Petersen's graph and a tour that cannot close. The words of length 5 with 2 ones, joined when disjoint (10 vertices, 15 edges), with an open tour through every vertex drawn heavy.

    The symmetric graphs no tour can close

    Take the words of five places with two ones and join two when they share no one. The ten words look exactly alike to the graph, and no closed tour runs through them — because every way of leaving out one edge at each word leaves two pentagons. Only four connected graphs this symmetric are known to fail like that, and nobody knows whether a fifth exists.

    part 4 · discrete
  5. Closing a path into a tour: the crossing pair the counting forces. A path through 10 points in a row, arcs from its two ends to their neighbours, and the crossing pair at step 3 whose two arcs replace that step to make a closed tour.

    Half the neighbours forces a tour

    Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.

    part 5 · discrete
  6. A closed knight's tour of the 8 × 8 board. A 8 by 8 chequered board with a closed polygon joining the centres of all 64 squares in the order a knight visits them.

    The boards a knight can tour

    A knight can visit every square of a chessboard once and land a move from where it began. On a 5 × 5 board it cannot, on a 4 × 100 board it cannot, and on a 3 × 8 board it cannot, though on 3 × 10 it can in sixteen ways. Allen Schwenk found in 1991 the complete list of rectangles without a closed tour, and the reasons on it are of two kinds — a colouring that counts squares, and a second colouring that a tour would have to make agree with the first.

    part 6 · discrete
  7. A tour appears the moment it can. n=16: τ2=27; tour 0-7-6-9-12-13-8-15-11-10-4-14-1-2-3-5; last point 10.

    The tour arrives with the last second neighbour

    Add the edges between n points one at a time in a random order. A tour through every point cannot exist while some point has fewer than two neighbours, and in a large random graph that is the only thing stopping it: the tour appears at the very edge that gives the last point its second neighbour. Watched in thousands of small graphs, the coincidence is already the rule, and the exceptions are tiny traps around the points of lowest degree.

    part 7 · discrete
  8. The shortest solution runs along one side (3 discs). Hanoi graph with 3 discs: 27 states; route classic of 8 states.

    One tour through every position of the Tower of Hanoi

    Draw every position of the Tower of Hanoi as a point and every legal move as a line, and the picture is a Sierpiński triangle. The famous shortest solution runs straight down one side of it, spelling the binary Gray code as it goes. The slowest honest solution threads through every position once and spells the ternary one. And unlike the cube the binary Gray code walks, which has 1,344 closed tours at four dimensions, the triangle has exactly one at every size.

    part 8 · discrete

All series