MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $P$ be a simple polygon defined by $n$ unit-length segments connecting lattice points of $\mathbb{Z}^2$. I have two operations that preserve the perimeter of $P$. The first is the "pop" of a corner either inward or outward; the second is pushing in a 3-edge "tab" at one spot and immediately pushing out a tab at another. Both operations are only applied if they preserve simplicity (non-self-intersection):
My question is:

What is the limit shape of $P$ as $n \rightarrow \infty$ and the operations are applied randomly for sufficiently many iterations?

I realize this question is imprecise. Perhaps the limit shape depends on the frequency balance between the two operations, which I have not specified. In addition, I am not quite sure how to best to describe a shape. But even an intuitive answer would be useful: Will the shape tend toward a convex-like blob, or toward a more spidery shape? (My guess is the latter.)

I was hoping to get a sense with small experiments as below, but it may require much larger $n$ and many more iterations for a clear pattern to emerge. I would appreciate any help in sharpening the question, answering it in some form, or pointers to related literature that could shed light on the issue. Thanks!

(The animation shows 800 operations. The green dot executing a random walk is the centroid of the vertices. The starting configuration is a crenellated square.)

share|cite|improve this question
I think the first picture is not correct (?) and the second rule changes perimeter (?). One possible idea is to represent a configuration as a word ($a^{\pm 1}$ for horizontal edges, $b^{\pm 1}$ for vertical edges). Your substitutions give some rewriting rules $ba\leftrightarrow ab$, (if I understand your first rule correctly) and $a\leftrightarrow bab^{-1}$, $b\leftrightarrow aba^{-1}$, and you want to look at the limit words. – Mark Sapir Nov 30 '11 at 1:26
@Mark: Thanks for catching that; fixed the corner-pop move. I didn't explain the other move well: it pushes a 3-edge tab down to one edge, and elsewhere pops up an edge to a 3-edge tab. Cool idea to view it as symbol rewriting and limit words! Thanks! – Joseph O'Rourke Nov 30 '11 at 1:49
What you are constructing is van Kampen diagrams over the grouppresentation $ab=ba$. Your moves amount to adding and removing cells (squares) of the diagram. Random diagrams have been considered, say, here: Myasnikov, Alexei; Ushakov, Alexander Random van Kampen diagrams and algorithmic problems in groups. Groups Complex. Cryptol. 3 (2011), no. 1, 121–185. Random diagrams do look "spidery". – Mark Sapir Nov 30 '11 at 2:23
@Mark: Thanks for the key term "van Kampen diagrams" (which I did not know) and the reference, which I will explore! – Joseph O'Rourke Nov 30 '11 at 2:29

Following up on Nathanael's answer: let me give a more precise statement about the dynamics as I understand it. At each step, choose whether you want to pop or push/unpush, then pick a location (or two in the push/unpush case) on the loop at random, and only then look if the operation you want to perform is legal or not (in particular, only then look at whether the loop has a corner at the selected location); if it is, perform it, if not, do nothing.

This is as opposed to the other natural version, which is if you want to pop, pick a place where it can be done at random and do it there - then I have no idea what happens.

The main difference is that with the first option, it is easy to check that the uniform measure is reversible for the dynamics, and hence in particular it is invariant. Then the question is mapped to one of irreducibility, i.e. to a deterministic question: can you, from any given shape, deform it into any other by a sequence of legal moves ? If you can, then indeed the chain converges in distribution to the uniform measure; if you can't, then it becomes a lot trickier. If it is indeed irreducible, then it might provide a good way to generate a self-avoiding polygon at random!

One reference on a very related topic is Sokal's work on the "pivot algorithm" for the SAW (where if you are not careful about exactly which moves are available, the chain is not irreducible and there are frozen configurations).

share|cite|improve this answer
@Vincent: Thanks for your illuminating comments! My implementation is following your second "natural version," but of course I could change that. Indeed my goal is to generate random SAPs. And indeed, all shapes are connected by legal moves. – Joseph O'Rourke Dec 2 '11 at 12:54
One quick note - if you define the second "natural way" appropriately, the distribution of the first move that is actually performed will be the same in both cases. That involves computing the number of legal moves of each type before deciding whether you want to pop or push though... but it should speed up the algorithm. Second note - Tom Kennedy did a lot of simulations of SAWs, he should know more about things like convergence times. – Vincent Beffara Dec 2 '11 at 13:57
@Vincent: Thanks again, these connections are very useful! – Joseph O'Rourke Dec 2 '11 at 18:10

The closest thing that comes to mind is the uniform measure on (self-avoiding) polygons with given perimeter. For this there are numerous predictions by physicists: eg, it should be related in the scaling limit to SLE with $\kappa= 8/3$ and so have a fractal dimension of $4/3$

Here the uniform measure is not (or at least, not obviously) the invariant measure of the chain, but maybe on sufficiently large scales it is not so different?

share|cite|improve this answer
@Nathanael: Thanks for mentioning the connection to the Schramm–Loewner Evolution (SLE)! – Joseph O'Rourke Dec 1 '11 at 1:38
@ Vincent : Thanks ! The version you suggest is indeed more natural in that it is easy to check the uniform measure is reversible. There should be a way to say that the invariant measures of both chains are pretty similar! (ps. sorry the comment doesn't really fit here but that's the only place MO will allow me to add a comment ... ) – Nathanael Berestycki Dec 2 '11 at 22:28

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.