Mathematical Aspect¶
Domino tilling¶
A domino tiling of a domain is a way to cover it with dominos without overlaps. For a given domain, there are only finitely many ways (possibly none at all) to cover is with dominos. We can pick one at random, giving the same probability to all of them. This is what we will always mean by a random domino tiling.
Tilings of an aztec diamond¶
The Aztec diamond of size n is this domain:
The main idea is that, since we select one out of many tilings, the main step will involve counting tilings having a certain behavior. A domino has two squares, so a domain with an odd number of squares cannot be covered by dominos The domain is assumed to be drawn on a chess board. This explains the difference in colors between the dominos.
We got here an example of an aztec diamond with order 4 :
The aztec diamond of order n got :
A domino tiling is a complicated mathematical object. We would like to encode it into a simpler one. The height function is defined by a local rule: around a black square, turning counterclockwise, it increases by 1 along every edge, except when crossing a domino (in which case it decreases by 3).
One important remark: the height function on the boundary of a given domain does not depend on the tiling.
On the Aztec diamond, it looks like a jigsaw.
Take a sequence of domains of the same shape, but larger and larger. Then look at the height function generated by a random tiling of each one.
Theorem : The height function approaches a deterministic, well characterized shape (which depends on the domain shape).
- On the arctic circle, the shape of the height function becomes interesting:
it is slanted in the corners;
and it is flat in the middle.
Shuffling algorithm¶
We will see how to randomly generate a tiling by getting a paving of size n from a paving of size n-1.
Cell 2*2 square :
-Destruction : if the active cell contains two dominoes, they are removed.
-Slip : if the active cell contains a domino, it is dragged.
-Create : if the active cell does not contain a domino, we flip a coin.
