Random polycube shapes

2011-05-18T21:34:01Z

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!):

Answer by Omer for Random polycube shapes

2011-05-21T17:52:54Z

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.

Random polycube shapes - MathOverflow

Random polycube shapes

Answer by Omer for Random polycube shapes