|
|
Discrete Mathematics and Optimization Seminar
|
Jan 10th, 2011
|
Domino shuffling for the Half-Hexagon 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 "half-hexagons". These graphs have some remarkable similarities to the well-studied Aztec diamond graph. For instance, the order-n aztec diamond and the order-n half-hexagon 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 half-hexagon 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, space-efficient random generation of perfect matchings, and will likely provide a good way to study large-n limiting behaviour (limiting shape, random matrix universality, and so forth.)
This is joint work with Eric Nordenstam (Universitat Wien).
|
|
|
|