Benjamin Young: Domino shuffling on a different lattice
Abstract
The "Domino shuffling algorithm" of Elkies, Kuperberg, Larsen and
Propp is a (somewhat) random, locally defined map on the set of domino
tilings of portions of the square lattice. Domino shuffling can be used to
count perfect matchings on an Aztec diamond graph, and to sample uniformly
from the set of such matchings. Analysis of domino shuffling gave rise to
the first proof of an Arctic Circle theorem (Jockusch, Propp and Shor) and
its asymptotics continue to be studied today (Nordenstam; Borodin). Domino
shuffling has also resolved some enumerative questions that come from
algebraic geometry (Y.)
In recent joint work with Cyndie Cottrell, we worked out a version of domino
shuffling which works on a different graph: namely the hexagonal honeycomb
graph superimposed on its dual triangular lattice. We can use our shuffle
to reprove a result of Ciucu, counting the tilings of an "Aztec Dragon"; we
also handle a related family of tiling problems. In addition, we expect
that much of the other work done on the square lattice will carry over
relatively easily to our shuffling algorithm.