COMPUTING SCIENCE

# The Science of Sticky Spheres

On the strange attraction of spheres that like to stick together

# From Geometry to Graph Theory

All the essential facts about sphere-to-sphere contacts in a cluster can be captured in a graph—a collection of vertices and edges. Each sphere is represented by a vertex, and two vertices are connected by an edge if and only if the corresponding spheres are in contact. The same information can be encoded even more abstractly in an adjacency matrix. A cluster of *n* spheres becomes an *n*-by-*n* matrix of 0s and 1s. The matrix element at the intersection of row *i* and column *j* is 1 if sphere *i* touches sphere *j* and otherwise is 0.

Given a cluster of spheres, it’s easy to construct the corresponding graph or adjacency matrix. But is it possible to go the other way—to start with an adjacency matrix and recover the full geometry of the cluster? In other words, with nothing more to go on than a table indicating which spheres are in contact, can one determine the coordinates of all the spheres in three-dimensional space? The answer is: Not always. Consider the all-0s matrix, which reveals nothing about the locations of the spheres except that they’re not touching. And the all-1s matrix describes a cluster that simply cannot exist when *n* is greater than 4. But for an important class of clusters the adjacency matrix does supply enough information to allow a full reconstruction. That class includes the clusters that maximize contact number. These facts suggest a direct problem-solving strategy: Generate all the candidate matrices and check to see which ones produce geometrically feasible clusters.

How many adjacency matrices need to be tested? Because contact is a symmetric relation—if *i* touches *j*, then *j* touches *i*—all the information in the matrix is confined to the upper triangle, which has *n*(*n*–1)/2 elements. Each element has two possible values, and so the total number of adjacency matrices is 2^{n(n–1)/2}.

Sifting through 2^{n(n–1)/2} matrices would be a formidable task; the value of this expression is already beyond two million at *n*=7 and exceeds 10^{16} at *n*=11. But not all of those matrices are distinct; many of them represent mere relabelings of the same graph. When redundancies of this kind are eliminated, the number of distinct 7×7 matrices is reduced from 2,097,152 to just 1,044.

Arkus and her group took advantage of a further dramatic winnowing. For reasons that will be explained below, they examined only matrices that meet two criteria: Every column and row has at least three 1s, and the total number of 1s in the upper triangle is 3*n*–6. For *n*=7, imposing these constraints reduces the number of candidate adjacency matrices from 1,044 to just 29. Among those 29 matrices, only five give rise to genuine three-dimensional sphere packings.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: Restoring Depth to Leonardo’s Mona Lisa

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations