Packing twelve spherical caps to maximize tangencies

Question

Suppose that $v_i$, for $i \in \{1, 2, \ldots 11, 12\}$, are twelve unit length vectors based at the origin in $R^3$. Suppose that $|v_i - v_j| \geq 1$ for all $i \neq j$. What arrangement of the $v_i$ maximizes the number of pairs $\{i,j\}$ so that $|v_i - v_j| = 1$?

If C is a cube of sidelength $\sqrt{2}$ centered at the origin then we can place the $v_i$ at the midpoints of the twelve edges. Taking the convex hull of the $v_i$ gives a cube-octahedron of edge-length one. See here for a picture. If you cut the cubeoctahedron along a hexagonal equator and rotate the top half by sixty degrees you get another polyhedron. Both of these have 24 edges. Are these the unique maximal solutions to the above problem?

Notice that if you place the $v_i$ at the arguably nicer vertices of a icosahedron then the $v_i$ become too widely separated. It is easy to check this by making a physical model!

I spent some time thinking about areas of spherical polygons and restrictions on the graph of edges (and its dual graph) coming from the Euler characteristic. However, I don't think I got very far - in particular ruling out pentagons seems to be a crucial point that I couldn't deal with. Finally, to explain the problem title: instead of thinking of unit vectors with spacing restrictions, consider the (equivalent) problem of placing twelve identical spherical caps, of radius $\pi/12$, on the unit sphere with disjoint interiors in such a way as to maximize the number of points of tangency.

This question was asked of me by an applied mathematician. It comes from a problem involving packing balls in three-space, minimizing some quantity that is computed by knowing pairwise distances. The solution to the kissing problem thus justifies the "twelve" appearing in the problem statement. The projection of surrounding balls to a central one gives the spherical caps.

Answer 1

Interesting question. I can find answer using my program, which was made for solving Tammes problem for 13 points. But I need some time for answer.

UPD: I wrote program. Result: 24 is a maximal number of edges. I did in three steps. First, I enumerated planar graphs with 12 vertices with at least 25 edges, at most 5 edges in a vertex and at most hexagonal faces. Total number of suc graphs is 67497.

Second, I eliminated by linear programming by considering values of face angles as variables. My constrains was: 1. angle in triangle is ~1.2310 2. each angle no less than 1.2310 3. sum of angles around vertex is 2*pi 4. opposite angles of rectangle are equal 5. sum of non-opposite angles in rectangle between 3.607 and 3.8213

I solve feasibility of this LP problem (with some tolerance) After this step all graph were eliminated.

Answer 2

As an extension of the problem (which turns out to have some physical significance), we may consider what would happen if we were to allow the twelve vectors to "land" within the unit ball rather than exactly on the unit sphere, that is we allow $|v_i|\le1$.

In such a case we can construct an arrangement that allows as many as $30$ vector differences $v_i-v_j$ to have exactly unit norm. The vector orientations are to the vertices of a regular icosahedron, whose circumradius for unit edges is $(\sqrt{10+2\sqrt5})/4$; this is indeed less than $1$ because $2\sqrt5<2×3=6$. The value to four decimal places is $0.9511$. As one might expect, the vector heads are only slightly inside the boundary of the ball.

The thirty edges are in fact the absolute maximum number that can have equal lengths between twelve vertices of a convex polyhedron, for the Euler characteristic combined with the number of edges being at least $3/2$ times the number of faces limits the possible edge count on the convex hull.

The fact that the icosahedral arrangement is realized with vectors shorter than the edge length of the polyhedron has crossed over into the world of materials. Single metallic elements, whose atoms are all the same size, typically form classical close-packed crystal structures such as face-cemtered cubic or hexagonally close-packed, which can be extended periodically through space (and have only $24$ unit-norm vector differences in the coordination sphere). But the structure lacks flexibility for alloys where the atom sizes could be slightly different. The icosahedral coordination has this flexibility (at the expense of not being fully close-packed) because the larger atoms can coordinate icosahedrally around slightly smaller ones; many metallic alloys have been found to form icosahedral quasicristals.