Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am wondering if it is hopeless to obtain any firm results on the following model of a "random polycube shape." First, a polycube in $\mathbb{R}^3$ is a connected face-to-face gluing of unit cubes. (This is a term prominent in Computer Graphics.) By a random polycube shape I mean the following. Start with an $n \times n \times n$ polycube, forming a cube of side length $n$. For example, for $n=3$, we start with $3^3=27$ unit cubes.
Now iterate the following process: (1) Identify a random exposed cube face. (2) Adjoin a new cube there. (3) Remove a randomly selected cube on the boundary of the shape (i.e., a cube with at least one exposed face), but only if the resulting polycube remains connected (in the face-to-face dual). So the shape grows by one cube and shrinks by one cube, therefore always maintaining $n^3$ cubes, and always maintaining connectivity.

I am interested in even gross parameters: What is the mean diameter $d$ (longest cube-to-cube path in the dual) of the shape? How does the genus $g$ grow as a function of $n$? Presumably both $d \rightarrow \infty$ and $g \rightarrow \infty$ as $n \rightarrow \infty$, but it might be difficult to determine the rates of growth. Pointers to relevant related literature would be appreciated. Thanks!

The (distracting!) animation below (a snapshot every 100 iterations over 10000 iterations) may not animate in your browser (Also, it, at points, wanders "off-screen"—double apology!):
     (animation here)

share|improve this question
Very interesting and awesome animation. Because you are working with polycubes, you might even need to expand from just asking about the genus to asking about the full homology since even in the $3\times 3\times 3$ case one can get an interior hole as soon as $t=3$, and the number of potential interior holes grows with $n$. –  ARupinski May 19 '11 at 1:08
@ARupinski Don't rules (1) and (3) require that cube additions / removals occur only for those with exposed faces, so that "interior holes" can't be formed? This seems to be the main difference between the "$n\times n\times n$ random polycubes shapes" as defined in the question and polycubes chosen uniformly from the set of all connected face-to-face gluing of $n^3$ unit cubes. –  j.c. May 19 '11 at 4:23
If someone is inclined to try to compute "experimentally" the genus, I suggest trying CHomP chomp.rutgers.edu/software by the group of Konstantin Mischaikow at Rutgers. I've played around with it before to compute the homology of other randomly created shapes made out of cubes. –  j.c. May 19 '11 at 4:27
One last comment: A good place to read about what's known about "polycubes chosen uniformly from the set of all connected face-to-face gluing of $n^3$ unit cubes" is the recent book "Polygons, Polyominoes and Polycubes", edited by A.J. Guttmann. –  j.c. May 19 '11 at 4:32
On the 3x3x3 setup: Add a cube on a corner, then delete a central face cube. Add another cube to a corner cube, then delete the interior cube. Finally, fill in the central face cube deleted in step 1 and delete one of the cubes you added to the corners. This leaves a hole in the interior and an extra cube sticking out on the exterior. Where does this sequence violate the rules you set out in the setup? –  ARupinski May 21 '11 at 18:05

1 Answer 1

up vote 8 down vote accepted

The objects you are interested in are called "lattice animals".

If you do not mind making slight modifications to your Markov chain, it is possible to make it reversible, so that the stationary distribution will be proportional to the number of boxes that can be removed while keeping the set connected. It is plausible that this number is concentrated, so that you will get approximately a uniformly random lattice animal.

In high dimension (above 8, i believe) these have been studied using lace expansion, and much is known. The graph diameter is of order $n^{1/2}$, and the graph is lose to a random tree. The $Z^n$ diameter is of order $n^{1/4}$. In low dimension these exponents change, and the problem seems much harder. (Compare to self avoiding walk in 3 dimensions.)

As for the genus, it should be linear in $n$, since small loops can appear almost anywhere using just a few boxes, so the entropy cost of adding loops is bounded. This is probably deducible from the lace expansion results in high dimension. This might be doable in lower dimensions as well, but seems hard.

share|improve this answer
@Omer: Thanks for this knowledgeable answer! I should have known the alternative name. I like the argument for linear growth of the genus--Nice! –  Joseph O'Rourke May 21 '11 at 20:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.