The University of Michigan Combinatorics Seminar


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. 