Rush Hour, Jr.

OK, so a black toddler and a Chinese toddler stumble on an international drug-trafficking ring — no, actually, this is a game I just bought for CJ, a kid’s version of Nob Yoshigahara‘s classic game Rush Hour.  The object here is to get the small white truck to the edge of the board (the top edge, in the image here.)  The trucks in your way can’t move sideways or turn; they just go forward and back.

You play a captivating game like this and naturally you start abstracting out the underlying math problem.  Play Set enough and you can’t avoid thinking about affine caps.  Rush Hour has more to do with the geometry of configuration spaces; it reminds me of the “disk in a box” problems that people like Persi Diaconis and Matt Kahle work on.

So here’s a question — it doesn’t capture all the features of Rush Hour, but let’s start here.  Let X be the unit square, and let c be a parameter between 0 and 1, and let N be a large integer.  Let L be the set of line segments in X which are either horizontal of the form y = i/N or vertical of the form x = i/N.  A traffic jam is a choice of a length-c interval in each of the 2N +2 line segments in L, where we require that these intervals be pairwise disjoint.  The traffic jams naturally form a topological space, which we call T(N,c).  We say an interval (x,i/n),(x+c,i/n) in a traffic jam t is trapped if no traffic jam in the connected component of t contains the interval (0,i/n),(c,i/n).

Questions: For which values of (N,c) is T(N,c) connected?  In particular, is it connected almost always once it’s nonempty?  If not, when does T(N,c) have a “giant component”?  If there’s an interesting range of parameters where T(N,c) is not connected, what proportion of intervals do we expect to be trapped?

Hard discs, configuration spaces, kissing spheres, the 15 puzzle

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 is small, the space looks a lot like Conf(X,n,0), the configuration space of n distinct points in R.  But when is large (more than about .71) the system undergoes a “Kirkwood phase transition” and the balls are constrained to look something like a lattice packing.  You might think of the former case as modeling a liquid, and the latter as modeling a solid.  See Figure 5 of Persi’s paper for a nice illustration of this phenomenon.

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 for suitably large p and seeing what happens…

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.