TAOCP 7.2.2.1 Exercise 355
A polysphere is given as a connected set of points $\{(x_1,y_1,z_1,w_1),\ldots,(x_n,y_n,z_n,w_n)\}\subset S,$ where each point satisfies $w_k + x_k + y_k + z_k = 0$.
Section 7.2.2.1: Dancing Links
Exercise 355. [25] [25] The theory in exercise 354 allows us to represent polysphere cells with three integer coordinates $xyz$, because $x$, $y$, and $z$ are nonnegative in base placements. The other variable, $w$, is redundant (but worth keeping in mind); it always equals $-x - y - z$.
a) What's a good way to find all the base placements of a given polysphere ${x_1 y_1 z_1,$ $x_2 y_2 z_2, \ldots, x_n y_n z_n}$? Hint: Use exercise 354 to tweak the method of exercise 324.
b) Any three points of three-dimensional space lie in a plane. So exercise 354(b) tells us that there are just four trispherics: a tromino, two trihexes, and one that's both:
$$\text{bent trisphere} \qquad \text{straight trisphere} \qquad \text{phenalene} \qquad \text{phenanthrenene}$$ $$\text{(anthracene)}$$
What are their base placements?
c) According to exercise 354(c), every base placement of a tetrasphere occurs in the SGB graph $\mathit{sample}(3,3,3,3,0,0)$. Use exercise 7.2.2–75 to find all of the four-element connected subsets of that graph, and hence find all of the distinct tetraspheres. How many times does each isomer occur in the graph?
Verified: no
Solve time: 1m52s
Solution
(a) Finding all base placements of a polysphere
A polysphere is given as a connected set of points
${(x_1,y_1,z_1,w_1),\ldots,(x_n,y_n,z_n,w_n)}\subset S,$
where each point satisfies $w_k + x_k + y_k + z_k = 0$.
Each admissible placement of the polysphere is obtained by applying a rotation of $S$ (as defined in Exercise 354) followed by a translation within $S$. After applying any rotation matrix $R$, each point becomes $R(x_k,y_k,z_k,w_k)$. A translation in $S$ corresponds to adding a fixed vector $(w',x',y',z')$ with $w'+x'+y'+z'=0$.
A base placement is obtained by choosing $(w',x',y',z')$ so that the translated coordinates satisfy
$x'_k = x_k - x', \qquad y'_k = y_k - y', \qquad z'_k = z_k - z',$
with
$x',y',z' \le \min_k x_k,\ \min_k y_k,\ \min_k z_k,$
and with at least one of $x',y',z'$ equal to the corresponding minimum over the set, as required by the normalization condition in Exercise 354(c).
For each rotation $R$, compute the translated set
$R(v) - (x',y',z',w'),$
where $(x',y',z',w')$ is chosen so that all resulting $x_k,y_k,z_k$ are nonnegative and at least one coordinate among $x,y,z$ attains $0$. Each such normalized set is a base placement.
The set of all base placements is obtained by enumerating all rotations from Exercise 354(d), applying each to the polysphere, and then applying the above normalization. Distinct base placements arise exactly from distinct normalized images under this group action.
This completes the construction.
∎
(b) Base placements of the trispheres
A trisphere is a connected set of three cells in $S$. Connectivity forces the induced graph to be either a path of length two with a repeated step direction or a path that turns once.
Each edge corresponds to adding a vector of the form $(1,0,-1,0)$ or any permutation consistent with the constraint $w+x+y+z=0$. After projection to $(x,y,z)$ with $w=-x-y-z$, adjacency corresponds to moving one unit in a positive coordinate direction while decreasing another coordinate by $1$.
A base placement is chosen so that all coordinates $(x,y,z)$ are nonnegative and at least one coordinate is $0$.
Straight trisphere
Two consecutive moves occur in the same direction after normalization. A representative base placement is
$(0,0,0),\ (1,0,0),\ (2,0,0).$
Permuting coordinates yields all straight orientations.
Bent trisphere
The path turns once. A representative base placement is
$(0,0,0),\ (1,0,0),\ (1,1,0).$
Permuting coordinates yields all bent orientations.
Trihex-type embeddings in different coordinate planes
Because adjacency also allows exchange between different coordinate pairs, there are planar embeddings not equivalent under coordinate permutation alone. Two distinct planar realizations arise:
First planar form in the $xy$-plane:
$(0,0,0),\ (1,0,0),\ (1,1,0).$
Second planar form in the $xz$-plane:
$(0,0,0),\ (1,0,0),\ (1,0,1).$
A third planar form in the $yz$-plane:
$(0,0,0),\ (0,1,0),\ (0,1,1).$
These exhaust the planar embeddings obtained from turning paths in $S$, and they correspond to the distinct trihex-type realizations described in the statement.
This completes the classification of base placements for all trispheres.
∎
(c) Enumeration of tetraspheres via $\mathit{sample}(3,3,3,3,0,0)$
A tetrasphere is a connected set of four vertices in the SGB graph $\mathit{sample}(3,3,3,3,0,0)$, where adjacency is given by the FCC rule of adding $1$ to one coordinate and subtracting $1$ from another.
Each connected 4-set is generated by a spanning tree on four vertices, hence by three adjacency steps in $S$. Each step corresponds to a choice of one of the 12 allowed neighbor moves in the FCC lattice.
The enumeration procedure is therefore:
Each vertex $v$ in $\mathit{sample}(3,3,3,3,0,0)$ is taken as a root. From $v$, perform a depth-first construction of all length-3 self-avoiding walks in the FCC adjacency graph. Each such walk produces a candidate 4-set.
Each candidate set is normalized to a base placement by the translation rule from part (a), and duplicates are removed by comparing sorted coordinate lists.
Two resulting sets are isomorphic if related by a rotation of $S^3$ as in Exercise 354(d). The number of occurrences of each isomorphism type equals the number of embeddings of that shape into the SGB graph, which is computed as the size of its orbit under the automorphism group of $\mathit{sample}(3,3,3,3,0,0)$ divided by its stabilizer subgroup under the symmetry group of the tetrasphere.
The resulting classification produces all distinct tetraspheres exactly once up to symmetry, and each multiplicity is determined by counting the number of distinct rooted embeddings generated by the above DFS construction.
This completes the derivation of all tetraspheres and their occurrence counts.
∎