16
$\begingroup$

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.
  Polycubes
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)

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ 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$. $\endgroup$
    – ARupinski
    Commented May 19, 2011 at 1:08
  • $\begingroup$ @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. $\endgroup$
    – j.c.
    Commented May 19, 2011 at 4:23
  • $\begingroup$ 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. $\endgroup$
    – j.c.
    Commented May 19, 2011 at 4:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – j.c.
    Commented May 19, 2011 at 4:32
  • 1
    $\begingroup$ 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? $\endgroup$
    – ARupinski
    Commented May 21, 2011 at 18:05

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Omer: Thanks for this knowledgeable answer! I should have known the alternative name. I like the argument for linear growth of the genus--Nice! $\endgroup$
    – Joseph O'Rourke
    Commented May 21, 2011 at 20:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .