Persi Diaconis has a lovely article in this month’s Bulletin of the AMS about the “Markov chain Monte Carlo revolution.” I especially liked the discussion of the “hard disk model” for fluids, which was new to me. Suppose X is a region in the plane and r a small positive number; then we can denote by Conf(X,n,r) the subspace of X^n consisting of n-tuples (x_1, … x_n) such that the discs of radius r centered at the x_i don’t intersect. A natural statistic on Conf(X,n,r) is the “packing density”
the proportion of the area of X which is taken up by the discs. You can imagine Conf(X,n,r) as a model for the space of states of a substance whose molecules are represented by the discs — the molecules are forbidden to overlap, but are otherwise allowed to move freely. When 
Apparently, we don’t know very much about the topology of Conf(X,n,r). Of course, for very large r the configuration space is empty. When r = 0 it is the usual configuration space of n distinct points on X. You might imagine carrying out a kind of Morse-theoretic decomposition of Conf(X,n,0) as follows: for each n-tuple (x_1, … x_n) of distinct points on X, write
where d(x,x’) is the distance between points x and x’ of X. Then f seems a bit like a Morse function, and you can imagine building up Conf(X,n,0) by starting with a $0$-cell at each local minimum of f, then attaching 1-cells for each critical point with one negative eigenvalue, and so on. Of course, f is badly non-smooth! But you can imagine, I guess, replacing the maximum by an 
The most primitive topological question you can ask is whether Conf(X,n,r) is connected — that is, given two configurations of n hard r-discs in X, is there always room to move from one configuration to the other?
One special case of this question is, to my eye, particularly charming: given a configuration of discs, can you permute the discs arbitrarily? When the discs are packed almost as tightly as possible, you might expect a negative answer; but in practice, it seems that a very small amount of wiggle room is enough to re-order the discs any way you want.
Example 1: Suppose X is a unit sphere and r is pi/6 radians. Then a configuration of n disjoint r-discs on X is equivalent to a configuration of n disjoint unit spheres tangent to X. The “kissing spheres problem,” which goes back at least to Newton, asks: what is the maximal number of disjoint unit spheres that can be tangent to X? The answer is 12; for instance, one can arrange these spheres at the vertices of a regular icosahedron. This leaves a little room for the spheres to roll around; and it turns out that this small leeway is enough to allow one to permute the spheres by an arbitrary element of S_12! John Baez has a nice discussion of this in a very early episode of This Week’s Finds.
Example 2: Let X be a unit square, and take r = 1/8 and n = 15; then you can cut X into 16 squares of sidelength 1/2, and place a disc at the center of all the squares but the one in the lower left corner. (In the interest of writing this post quickly, I’ll leave you to draw your own picture of this.) Now this packing of discs is pretty tight — at the outset, only two of the discs have room to move. But it turns out that here, too, one can permute the discs in an almost arbitrary way; you can get any permutation in the alternating group A_15. In fact, this problem is nothing but a continuous version of the Sam Loyd “15” puzzle.
If you wanted to get a general sense of what was going on here, you might discretize the problem in the following way: suppose X is a graph with N vertices, n of which are covered by stones. You are allowed to move any stone to an adjacent empty vertex. Can you permute the stones in any way you like? If N = n, the answer is clearly no; there are no allowable rooms. But if you allow any wiggle room at all — that is, if you let n = N-1 — the answer, somewhat suprisingly to me, is essentially yes. This is a theorem of Wilson (“Graph Puzzles, Homotopy, the Alternating Group”) from 1974: if a graph X cannot be made disconnected by the removal of a singular vertex, and is not an N-cycle, then the N-1 stones can be permuted by any permutation in the alternating group, with one exception when N = 7.
What is this strange exceptional 7-vertex graph? See if you can figure it out! Or look here.
Quomodocumque 
Is there an (X, r) such that Conf(X, 6, r) is a continuous version of that exceptional graph? (My gut intuition was “yes,” but now that I think about it, the obvious construction doesn’t seem to work.)
Is it possible that the discs are arbitrarily permutable, but Conf(X,n,r) is not connected?
If Conf(X,n,r)/S_n (the space of unlabeled discs) is connected, then “disks are arbitrarily permutable” means the same thing as “Conf(X,n,r) is connected.” But in general, you might have a situation like the following — perhaps n and r are arranged in such a way that every configuration is either very close to L_1 or very close to L_2, where L_1 and L_2 are two particularly dense packings. Then the question of whether you can permute the discs in a “close to L_1” packing is separate from whether you can permute the discs in a “close to L_2” packing. Even if the answer to both questions is yes, Conf(X,n,r) will be disconnected, because you can’t get from “close to L_1” to “close to L_2.”
Do you know a simple example where you have the situation you describe, where the discs are permutable (within any configuration) but Conf(X,n,r) is disconnected? It seems to me that permutability gives quite a lot of freedom moving the discs around (but as you say, not so much freedom as to imply that Conf(X,n,r) is connected).
Not off the top of my head, no, but I don’t really have a feel for these things. I don’t even really know what to think the local minima of f (candidates for L_1 and L_2) look like. So when I say “you might have a situation like” the one I describe, I just mean “a priori you might” — I haven’t thought about whether such situations really arise.
I know it was a while ago, but I enjoyed this post. I am a postdoc at Stanford, working with both Persi and Gunnar, and I have thought a bit about the discs over the past couple years and have a few results.
Here is my blog entry on a recent arXiv post: http://matthewkahle.wordpress.com/2009/08/16/an-application-of-disc-packing-to-statistical-mechanics/
I have wondered the same thing: what is the symmetric group action on the set of path components induced by permuting discs? I don’t know that answer to this, or to Pontus’s question, and I think they are very interesting and relevant.
One idea for how you could topologically quantify that there is a lot of freedom if you can permute the discs is as follows. S_n now acts freely on this path component. So there has to be some nontrivial homology somewhere, by the Lefshetz fixed point theorem say, and we know it’s not in H_0, so there’s some nontrivial higher homology.
Also, together with undergraduate researcher and Gunnar Carlsson, we implemented a Morse theoretic approach to studying these spaces when n is small. We were able to recover the dendrogram for persistent path components, when n = 5, and even here there was a surprise or two. In particular, the number of path components was not monotone in the underlying radius, and path connectedness was not a monotone property.
In particular, the number of path components was not monotone in the underlying radius, and path connectedness was not a monotone property.
Whaaaaa-? Now that is weird.
[…] of G evaluated at N. When M is a box, Conf(G,M,b) is the “discs in a box” space I blogged about here. If M is (Z/2Z)^k with Hamming distance, you are asking about how many ways you can supply G with […]