Average degree of contact graph for balls in a box - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:01:11Z http://mathoverflow.net/feeds/question/71397 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71397/average-degree-of-contact-graph-for-balls-in-a-box Average degree of contact graph for balls in a box Joseph O'Rourke 2011-07-27T12:43:10Z 2011-08-02T20:09:03Z <p>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 <a href="http://en.wikipedia.org/wiki/Jamming_%28physics%29" rel="nofollow">jammed</a>.) Assume the box dimensions are much larger than the ball radius (unlike the image below), so that boundary effects are minimized. Define the <em>contact graph</em> of the configuration to have a node for each ball, and an arc for two balls in contact. <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/BallsInBox.n38d298074.jpg" alt="Balls in Box" /> <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <sub> <a href="http://www.randomwalk.de/sphere/incube/" rel="nofollow">Image</a> due to <a href="http://www.pfoertner.org/" rel="nofollow">Hugo Pfoertner</a> </sub> <br /></p> <blockquote> <p>What is the average degree of a node in the contact graph for balls in $\mathbb{R}^d$, under the scenario above?</p> </blockquote> <p>The maximum degree is the <a href="http://en.wikipedia.org/wiki/Kissing_number" rel="nofollow">kissing number</a>: 6 in $\mathbb{R}^2$, 12 in $\mathbb{R}^3$, 24 in $\mathbb{R}^4$. I am interested in two aspects:</p> <blockquote> <p>(1) Is the average contact degree known to be significantly smaller than the kissing number?</p> </blockquote> <p>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.</p> <blockquote> <p>(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.</p> </blockquote> <p>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?</p> <p>Any known structural properties of the contact graph for jammed configurations would be of interest. Thanks! <hr /> <b>Addendum.</b> The Torquato and Stillinger paper cited by Matthew Kahle (<em>Rev. Mod. Phys.</em> <b>82</b>, 2633–2672 (2010)) is a gold mine of information on the topic. Here is their Fig.14 showing three different "optimal strictly jammed" packings: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/Torquato.jpg" alt="Balls in Box" /> <br /> A configuration is <em>strictly jammed</em> if it is "collectively jammed" and furthermore "disallows all uniform volume-nonincreasing strains of the system boundary."</p> http://mathoverflow.net/questions/71397/average-degree-of-contact-graph-for-balls-in-a-box/71412#71412 Answer by jc for Average degree of contact graph for balls in a box jc 2011-07-27T15:11:34Z 2011-07-27T20:49:26Z <p>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 <b>soft</b> spheres in a <b>periodic</b> box <i>without</i> gravity. This is the study of <b>point J</b>. </p> <p>Here's an image of point J on the "<a href="http://www.physics.upenn.edu/liugroup/jamming.html" rel="nofollow">jamming phase diagram</a>" proposed by Andrea Liu and Sid Nagel, where the axes are different parameters one might tune in disordered packings:</p> <p><img src="http://www.physics.upenn.edu/liugroup/figs/jamming_phase_diagram3.png" alt="jamming phase diagram"></p> <p>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.</p> <p>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.</p> <p><a href="http://pre.aps.org/abstract/PRE/v68/i1/e011306" rel="nofollow">The 2003 paper of O'Hern, Silbert, Liu and Nagel</a> did extensive simulations in 2 and 3 dimensions of the above and found the following facts related to your query:</p> <p>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.</p> <p><img src="http://i583.photobucket.com/albums/ss275/jaspercrowne/width.png" alt="Width of distribution of jamming thresholds"></p> <p>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.</p> <p>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. </p> <p>Isostaticity refers to the <strong>emergence of mechanical rigidity</strong>: 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 <b>square root</b> 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?</p> <p><img src="http://i583.photobucket.com/albums/ss275/jaspercrowne/contactnumber.png" alt="contact number versus phi-phic"></p> <p>This plot shows how $Z-Z_c$ changes as a function of $\phi-\phi_c$.</p> <p>They found many other exponents and evidence for some <a href="http://en.wikipedia.org/wiki/Critical_phenomena" rel="nofollow">critical phenomena</a>-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. </p> <p>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 <a href="http://www.physics.leidenuniv.nl/sections/cm/grm/articles/cm10_3_033101.pdf" rel="nofollow">this one</a> by Martin van Hecke because it has a lot of colorful pictures, though there's also one by <a href="http://arxiv.org/abs/1006.2365" rel="nofollow">Liu et al</a>. These articles might also shed some light on how one might think about your system with hard balls, walls and gravity.</p> http://mathoverflow.net/questions/71397/average-degree-of-contact-graph-for-balls-in-a-box/71445#71445 Answer by Matthew Kahle for Average degree of contact graph for balls in a box Matthew Kahle 2011-07-27T22:46:43Z 2011-07-27T22:46:43Z <p>Torquato and Stillinger have a recent survey article that discusses some questions like this: <a href="http://rmp.aps.org/abstract/RMP/v82/i3/p2633_1" rel="nofollow">Jammed hard-particle packings: From Kepler to Bernal and beyond</a> </p> <p>They are particularly interested in random packings.</p> <p>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.</p>