LETTERS TO THE EDITORS
To the Editors:
In Brian Hayes’s Computing Science column “The Science of Sticky Spheres” (November–December), he said:
The challenge of pushing the frontier out to n = 11 was taken up by Hoy, Harwayne-Gidansky and O’Hern at Yale. They relied on many of the same methods but adopted a different approach to streamlining the algorithms. For example, they took advantage of a curious fact proved by Therese Biedl, Erik Demaine and others: Any valid packing of spheres has a continuous, unbranched path that threads from one sphere to the next throughout the structure, like a long polymer chain.
In the paper by Biedl, Demaine and others that Hayes cited, they did not prove (or even attempt to prove) that any rigid, finite packing of sticky spheres “has a continuous, unbranched path that threads from one sphere to the next throughout the structure,” because it is not true in general. Such a path is called Hamiltonian, named after mathematician William Rowan Hamilton, and not all valid packings of sticky spheres have a Hamiltonian path. The structure shown below, which I discovered with Erik Demaine and Martin Demaine, is an example of a packing that has no Hamiltonian path.
To build the structure, start with a pentagonal bipyramid with seven spheres, shown as a graph with unit-length edges, whose vertices represent the centers of the spheres. This structure is well known to be rigid. Then, attach nine more vertices with three unit lengths to 9 of the 10 triangular faces of the pentagonal bipyramid. These correspond to nine more spheres. So there are 7 + 9 = 16 vertices that correspond to a rigid arrangement of 16 sticky spheres.
This arrangement cannot have a Hamiltonian path. The reason is a simple counting argument: Suppose there is a Hamiltonian path. Because there are 16 vertices in all, the Hamiltonian path must have 15 edges. Each of the nine additional vertices is adjacent to two other edges in the Hamiltonian path, except possibly for the two end points of the path, which correspond to one edge of the path. This is a disjoint set of at least 2 x 9 – 2 = 16 edges, one more than there are in the path, a contradiction.
For further discussion of this issue, see http://bit-player.org/2013/sphere-packings-and-hamiltonian-paths.