Impossible patterns of sphere tangencies
My latest preprint, “Tangent spheres and integer distances” (arXiv:2606.18569, to appear at CCCG), involves the patterns of external tangencies of circles, spheres or higher-dimensional hyperspheres. You can make a graph whose vertices are a given set of spheres and whose edges are pairs of externally-tangent spheres, and I’d like to understand which graphs are possible. By the circle packing theorem, any planar graph can be represented by interior-disjoint circles in this way, but here I’m not requiring disjointness. So, for instance, you can represent any unit distance graph in the plane (such as the Petersen graph below) by expanding each vertex of the graph into a unit-diameter circle.
In three dimensions, you can produce spheres whose tangencies form arbitrarily large complete bipartite graphs \(K_{n,n}\) by placing \(n\) spheres interior to a torus, like a ball-bearing race or those cat toys with balls rolling around a toroidal track, and another \(n\) spheres tangent to them, centered on the axis of the torus. And by a form of Descartes’ theorem, any four mutually tangent spheres (a \(K_4\) graph of tangencies) can be completed to a \(K_5\) in two different ways, but the two added spheres are not tangent to each other, so one cannot form a \(K_6\) graph.
Given these examples, you might think that it is the high local connectivity of the complete graph \(K_6\) that makes it unrealizable, and the local independence of the complete bipartite graph \(K_{n,n}\) (each vertex has an independent set of neighbors) that makes it realizable. But things are more subtle than that. For every odd \(k\) I can prove the existence of a graph in which each vertex has an independent set of six neighbors, the shortest odd cycle has length \(k\), and there is no realization as a subgraph of external tangencies in \(\mathbb{R}^3\).
This follows from the main lemma in the paper: if a system of spheres or hyperspheres in \(\mathbb{R}^d\) has external tangencies that include a subgraph of the form \(K_{a,b}\), with both \(a\) and \(b\) having at least three spheres, then the sets of spheres on each of the two sides of this bipartite graph have centers that lie on a hyperplane. This is trivial in two dimensions (no such system can exist because it would lead to a planar drawing of \(K_{3,3}\)) but as we have seen, even three-dimensional spheres can have arbitrarily large complete bipartite graphs. Another famous system of spheres, Soddy’s hexlet, has a \(K_{3,6}\) subgraph, and spheres with the tangency graph \(K_{2,2,2,2}\) have many \(K_{4,4}\) subgraphs. (The image below shows Soddy’s hexlet in a form where two of the spheres have degenerated to flat planes.) The lemma applies to these configurations and proves that the subsets of spheres on each side of each bipartition have coplanar centers. The paper then uses this lemma to prove that in localization from differences of distances to landmarks (as used by GPS), any four non-coplanar landmarks suffice, and to generalize the Erdős–Anning theorem, that Euclidean point sets with integer distances are finite or collinear, to arbitrary-dimensional hyperbolic spaces.
So let’s use the same lemma to construct a graph with no short odd cycles and small independent sets of neighbors for each vertex, that cannot be realized by spheres in \(\mathbb{R}^3\). To do so, blow up each vertex of a \(k\)-cycle by replacing it with an independent set of three vertices. Here’s a confluent drawing for \(k=5\) and \(d=3\):
Suppose that this graph had a realization as the external tangencies of spheres in \(\mathbb{R}^3\). No two spheres in a blown-up triple of spheres can be concentric, because concentric spheres could not be tangent to the same neighbors. Each triple \(T\) of spheres (no two concentric), has a unique circle (or degenerate line) \(O_T\) orthogonal to \(T\), the circle or line through the centers of the spheres in \(T\). Any Möbius transformation of space takes circles to circles and spheres to spheres and preserves tangency and orthogonality, so the transformation of the circle \(O_T\) is the circle \(O_{T'}\) for the transformed triple \(T'\). We can perturb the realization by a Möbius transformation so that external tangencies remain external and so that, after this perturbation, the point at infinity does not lie on any \(O_T\). After this perturbation, none of the \(O_T\) degenerate to lines, and therefore the centers of each triple of spheres determine a unique plane. By the lemma from the preprint, each pair of triples two steps along the cycle from each other have centers that lie on the same plane, and because the cycle has odd length, all spheres have coplanar centers. But then this realization would continue to be valid in the plane of all the sphere centers, and we already know that the many \(K_{3,3}\) subgraphs of this graph cannot be realized in the plane. This contradiction means that the supposed three-dimensional realization of our blown-up cycle graph cannot exist.
In four or more dimensions, the second part of the argument still shows that the \(d\)-blowup of a \(k\)-cycle has no realization with sphere centers in each blown-up \(d\)-tuple of spheres in general position. But the first part, where we use a Möbius transformation to perturb everything into general position, stops working. If one blown-up \(d\)-tuple of spheres has cocircular centers, like the ball bearing cat toy example in 3d, its two neighboring \(d\)-tuples can each be placed on lines orthogonal to the circle and through its center, but in four dimensions there is a whole plane orthogonal to a circle and through its center. We can choose two different lines on this plane, and then different circles orthogonal to each of these lines, etc., creating enough flexibility as one progresses around the cycle that a realization might be possible. But my powers of four-dimensional visualization aren’t strong enough for me to be certain that this works, and it might still be possible to prove that other locally independent graphs are unrealizable.