Matpic
mathematics, in pictures
Series

Hamiltonian cycles — the series

4 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

All series