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.


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.

| cite | improve this answer | |
  • $\begingroup$ Are there other solutions with 24 edges other than the ones given by Sam Nead? $\endgroup$ – j.c. May 18 '10 at 15:42
  • $\begingroup$ I see, by staring at the dihedral angle of a tetrahedron, that the vertex degrees are either 1, 2, 3, 4, or 5. A "sliding" argument rules out degrees equal to 1. But I don't see why the face degrees are less than seven. (In fact, the original poser showed me another sliding argument to convince me that all faces are disks, ie rule out annular or worse faces.) Also, how do you get the upper and lower bounds on the sum of a pair of adjacent angles of a rombus? (Is the maximum really realized at $2\pi - 2 \arccos(1/3)$ or does it just "look" that way?) $\endgroup$ – Sam Nead May 18 '10 at 17:03
  • $\begingroup$ I was wrong then exclude septagons. I did it for Tammes problem because where is lemma that septagons are impossible for irreducible graphs. But here they are not irreducible. I will recalculate with all faces tomorrow (as well question for 24 edges). About rhombus, from spherical Pythagorean theorem where is constrain : $cot(a/2)*cot(b/2) = cos d$, where d - length of the side, a,b - angles. Maximum sum of angles applies for regular quadrilateral, so yes maximal summ is $2 pi - 2 \arccos(1/3)$ $\endgroup$ – Alexey Tarasov May 18 '10 at 17:46
  • 4
    $\begingroup$ I recalculated for all good graphs. Total amount of graphs with 24 edges and more is 221501. By elimination program only two graph were survived. These graphs are described in the question. Does anybody know about existing non-computer proof of this fact? $\endgroup$ – Alexey Tarasov May 19 '10 at 16:22
  • 1
    $\begingroup$ I was fast because I already have working approach. Graphs are generated by program plantri and filtered by my program. Total times about 15 minutes. Program for solving Tammes problem for N=13 is quite complicated. It is written on the perl it's size 1800 lines. Part used here more simple. Program will available soon on my webpage with dcs.isa.ru/taras/tammes13 $\endgroup$ – Alexey Tarasov May 21 '10 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.