
Discrete Mathematics and Optimization Seminar

Jan 10th, 2011
Domino shuffling for the HalfHexagon graph
Ben Young
Mathematical Sciences Research Institute

Abstract:
I will discuss some recent work done this fall at MSRI. We discovered a nice family of planar bipartite graphs which we call "halfhexagons". These graphs have some remarkable similarities to the wellstudied Aztec diamond graph. For instance, the ordern aztec diamond and the ordern halfhexagon both have the same number of perfect matchings, 2^(n(n+1)/2).
We tried (unsuccessfully) to find a bijection between these structures. However, to our surprise, we were able to construct a "domino shuffling algorithm" on the halfhexagon which is strikingly similar to that of the Aztec diamond. This procedure, though random, has very nice combinatorics and provides an easy proof of the above count. It also allows fast, unbiased, spaceefficient random generation of perfect matchings, and will likely provide a good way to study largen limiting behaviour (limiting shape, random matrix universality, and so forth.)
This is joint work with Eric Nordenstam (Universitat Wien).



