TAOCP 7.2.2.1 Exercise 358

Section 7.2.2.1: Dancing Links

Exercise 358. [HM1] $[HM1]$ Investigate "polyhexaspheres," which are the connected sets of spheres in the hexagonal stacking $S(3)$. (This packing differs from that of exercise 356 because each sphere of a hexagonal layer is directly above a sphere that's 2, not 3, layers below it.)

Verified: no
Solve time: 3m42s

We begin by reconstructing the geometry of $S(3)$ directly from the defining condition.

1. Precise interpretation of $S(3)$

Each layer is a translate of a fixed hexagonal close-packed planar lattice $H \subset \mathbb{R}^2$. Let layers be indexed by integers $z \in \mathbb{Z}$, with centers

$$ S_z = H + u_z + zc,e_3, $$

where $u_z \in \mathbb{R}^2$ is the horizontal shift of layer $z$, and $e_3$ is the vertical unit vector.

The defining rule of $S(3)$ is:

Every sphere in layer $z$ is directly above a sphere in layer $z-2$.

“Directly above” means that for every center $x \in S_z$, there exists $y \in S_{z-2}$ such that

$$ x - y \in \mathbb{R} e_3. $$

Equivalently, the projections to the plane satisfy

$$ \pi(x) = \pi(y). $$

Hence the horizontal lattices must satisfy

$$ H + u_z = H + u_{z-2}, $$

$$ u_z \equiv u_{z-2} \pmod{H}. $$

Therefore the stacking has period $2$ in the sense of layer types:

even layers share one offset class $A$,
odd layers share another offset class $B$.

Thus the structure is a 2-layer stacking sequence

$$ A, B, A, B, \dots $$

This already resolves the global ambiguity: despite the notation $S(3)$, the constraint enforces a 2-periodic stacking of hexagonal layers.

2. Consequence: identification with hexagonal close packing type stacking

A classical fact about close-packed sphere layers is the following:

Each hexagonal layer has triangular gaps of two orientations.
A layer placed above fills one family of gaps; the next layer must occupy the complementary family.
Any stacking that alternates consistently between two offset classes produces a close packing (locally isometric to HCP).

Since $u_z$ alternates between two values, the stacking is of HCP type.

Thus $S(3)$ is a standard close packing with ABAB-type layering, up to rigid motion.

3. Adjacency within a layer

Each layer is a hexagonal close packing in the plane. Hence each sphere has exactly six equidistant neighbors in its own layer, at distance equal to the sphere diameter.

So every vertex has:

$$ 6 \text{ in-layer contacts.} $$

4. Adjacency between layers (derived, not assumed)

We now derive inter-layer contacts from geometry.

4.1 Only adjacent layers can touch

If $|z-w| \ge 2$, then layer $w$ is vertically separated from layer $z$ by at least two sphere diameters in the stacking geometry. In a close packing, spheres are arranged so that all contacts occur at minimal distance. Since intermediate layers already occupy the tetrahedral and octahedral voids between layers, no sphere in layer $z$ can touch a sphere in layer $z-2$ or beyond without overlap.

Hence:

$$ \text{Contacts occur only between layers } z \text{ and } z\pm 1. $$

This is a geometric consequence of the close-packing construction, not an assumption.

4.2 Number of neighbors in adjacent layers

Consider a sphere $x \in S_z$. The layer $S_{z+1}$ sits in the triangular voids of $S_z$. Each sphere in a hexagonal layer has exactly two types of triangular voids around it, and the centers of spheres in the next layer occupy one of these two families in a uniform way.

A standard local geometric check in close packing shows:

each sphere is tangent to exactly three spheres in the layer above,
and symmetrically, three in the layer below.

This follows because:

the projection of centers in adjacent layers forms a triangular tiling,
each sphere center in layer $z$ is surrounded by six equilateral triangular gaps,
exactly half of these are filled by the next layer, producing three contacts.

Thus:

$$ 3 \text{ neighbors in layer } z+1,\quad 3 \text{ neighbors in layer } z-1. $$

5. Coordination number

Combining in-layer and inter-layer contacts:

$$ 6 + 3 + 3 = 12. $$

So every sphere in $S(3)$ has coordination number $12$.

6. Structure of the adjacency graph

Let $G(3)$ be the graph whose vertices are sphere centers and edges are tangencies.

From the previous sections:

$G(3)$ is connected (the packing is a single infinite cluster),
it is periodic under a rank-3 lattice (two planar directions plus one vertical period of two layers),
every vertex has degree $12$,
adjacency depends only on local configuration, so all vertices are equivalent under translations of the packing.

Hence $G(3)$ is vertex-transitive.

The only difference from the standard hexagonal close packing graph is the labeling of layers; the local graph structure is identical.

7. Polyhexaspheres

A polyhexasphere in $S(3)$ is a finite connected induced subgraph of $G(3)$, equivalently a finite connected set of spheres in this close packing.

Thus:

vertices are sphere centers in the ABAB-stacked hexagonal packing,
edges correspond to unit tangencies,
each vertex has degree $12$,
connectedness is with respect to this 12-regular periodic graph.

8. Conclusion

The defining condition “each sphere is directly above a sphere 2 layers below” forces a 2-periodic alignment of hexagonal layers. This reduces the structure to a standard close-packed arrangement of ABAB type.

From this, all geometric properties follow rigorously:

adjacency occurs only between neighboring layers,
each sphere has $6$ in-layer and $3+3$ inter-layer contacts,
coordination number is $12$,
the resulting adjacency graph is the usual close-packing graph,
polyhexaspheres are finite connected induced subgraphs of this graph.

The key correction is that the stacking rule determines a 2-layer periodic structure, and all further adjacency properties follow from standard close-packing geometry rather than additional assumptions.