# Average degree of contact graph for balls in a box

Imagine you dump congruent, hard, frictionless balls in a box, letting gravity compress the balls into a stable configuration (I believe such configurations are called jammed.) Assume the box dimensions are much larger than the ball radius (unlike the image below), so that boundary effects are minimized. Define the contact graph of the configuration to have a node for each ball, and an arc for two balls in contact. Image due to Hugo Pfoertner

What is the average degree of a node in the contact graph for balls in $\mathbb{R}^d$, under the scenario above?

The maximum degree is the kissing number: 6 in $\mathbb{R}^2$, 12 in $\mathbb{R}^3$, 24 in $\mathbb{R}^4$. I am interested in two aspects:

(1) Is the average contact degree known to be significantly smaller than the kissing number?

I have seen results on the density of irregular packings (e.g., about 64% in $\mathbb{R}^3$ vs. 74% in an optimal packing), but I have not seen this expressed in terms of the structure of the contact graph.

(2) For large $d$, is it expected that the average contact degree increasingly deviates from the kissing number, or the opposite: that jammed packings approach the densest packings.

Perhaps one can only hope for an answer here for $d{=}24$, where the kissing number is known. But maybe there is a heuristic argument based on how much "room" there is around a ball in higher dimensions?

Any known structural properties of the contact graph for jammed configurations would be of interest. Thanks!

Addendum. The Torquato and Stillinger paper cited by Matthew Kahle (Rev. Mod. Phys. 82, 2633–2672 (2010)) is a gold mine of information on the topic. Here is their Fig.14 showing three different "optimal strictly jammed" packings: A configuration is strictly jammed if it is "collectively jammed" and furthermore "disallows all uniform volume-nonincreasing strains of the system boundary."

Torquato and Stillinger have a recent survey article that discusses some questions like this: Jammed hard-particle packings: From Kepler to Bernal and beyond

They are particularly interested in random packings.

A short answer to your question is that for hard spheres, it is generally believed that random jammed packings are close to "isostatic," meaning the average contact number is $2d$, where $d$ is the dimension.

• Thank you, Matthew, that article appears to be an exact hit on the topic. The $2d$ contact number is much smaller than I would have guessed; nice to have intuitions rattled! – Joseph O'Rourke Jul 28 '11 at 0:33

To me the most impressive work in the field of "jamming" physics is a web of not quite yet mathematically formulated conjectures discovered by extensive simulations on packings of soft spheres in a periodic box without gravity. This is the study of point J.

Here's an image of point J on the "jamming phase diagram" proposed by Andrea Liu and Sid Nagel, where the axes are different parameters one might tune in disordered packings: One considers "soft spheres" of radius $r$ interacting with a potential energy which is zero until they overlap (that is, the center-to-center distance is $2r$), after which, the energy increases with some low power of the separation, typically 2 (harmonic), 5/2 ("Hertzian") or some others. In 2D simulations in this field have mainly considered 1:1 mixtures of balls with radii in a ratio of 1.4:1 in order to prevent crystallization. The choice of these ratios is a historical convention, as far as I can tell. In 3D, balls tend not to crystallize as easily, so monodisperse ensembles of balls can be used.

Now the idea is to place $N$ such balls in a box with periodic boundary conditions and grow the balls slowly while minimizing the potential energy function by a conjugate gradient method. When the packing fraction $\phi$ is low, the balls will be able to space themselves out so that no balls overlap. When the packing fraction $\phi$ passes a critical $\phi_c$, the minimum energy state now has nonzero overlap, and the ball packing gains some solid-like properties, such as a shear modulus and bulk modulus (resistance to shear and compression, respectively). The system is then said to be jammed.

The 2003 paper of O'Hern, Silbert, Liu and Nagel did extensive simulations in 2 and 3 dimensions of the above and found the following facts related to your query:

First, the packing fraction $\phi_c$ is configuration dependent for finite systems (that is for a given $N$, there is really a range of $\phi_c$ at which the system jams), but as $N$ increases, this range narrows, and it's natural to conjecture that in "the thermodynamic limit", there is a well-defined packing fraction at which such soft spheres jam, called point J. For 2D bidisperse disks, it is around 0.84, for 3D balls, it is around 0.64. The above graph from their paper shows the width of the distribution of jamming thresholds as $N$ increases. Physicists love power laws because they lead to scaling exponents, which is why both this graph and the next are log-log plots.

Second, the average contact number (usually called $Z$) near point J has very interesting behavior (here contacts are defined to exist between any pair of particles which have nonzero overlap). Below jamming, obviously it is zero since the balls don't overlap. But once you reach $\phi_c$, the contact number jumps to $Z_c=$twice the dimension. This is why point J is often called an isostatic point.

Isostaticity refers to the emergence of mechanical rigidity: a naïve balancing of constraints (one per contact between particles, or $NZ/2$) and degrees of freedom ($dN$) for a set of $d$-dimensional balls leads to $Z=2d$. If one increases $\phi$ a little bit about $\phi_c$, one finds empirically that the contact number increases as the square root of $\phi-\phi_c$, independent of the potential and dimension. I don't know if this has been extensively tested in higher dimensions, but it's guessed that this is a generic feature of the jamming of soft spheres. Observe that $Z_c$ is much much lower than the kissing number, which I believe is expected to scale exponentially? This plot shows how $Z-Z_c$ changes as a function of $\phi-\phi_c$.

They found many other exponents and evidence for some critical phenomena-like behavior in this paper which I'm afraid I won't be able to explain here. Suffice it to say that this paper has inspired quite a bit of work in the soft condensed matter community. The conjectures I hinted at above are basically to try to make rigorous any of the empirical observations found in this paper or in this field of inquiry, more broadly.

In the last few years a few overviews for physicists have come out, which might also be interesting reading for broad-minded mathematicians. I like this one by Martin van Hecke because it has a lot of colorful pictures, though there's also one by Liu et al. These articles might also shed some light on how one might think about your system with hard balls, walls and gravity.

Edit, July 26, 2017: Since I wrote this answer (almost exactly 6 years ago!), there have been many exciting developments in the study of jamming of hard spheres related to "the exact solution of the hard sphere model in infinite dimensions" by Charbonneau, Kurchan, Parisi, Urbani, Zamponi and others. It is impossible for me to summarize this theory since it relies on techniques well outside my area of expertise, however a review for physicists (written by the five named authors in the previous sentence) can be found here.

• Wow! This is a rich answer! Yes, the kissing number must grow exponentially with dimension (just from volume considerations). I like the term "Point J"; a potential movie title (or postmodernist website, pointj.com). The $Z=2d$ contact number is intriguing. And the van Hecke paper is a treasure trove. Thanks so much! – Joseph O'Rourke Jul 27 '11 at 15:26