Stochastic Flips on Dimer Tilings
Thomas Fernique, Damien Regnault
Abstract
This paper introduces a Markov process inspired by the problem of quasicrystal growth. It acts over dimer tilings of the triangular grid by randomly performing local transformations, called flips, which do not increase the number of identical adjacent tiles (this number can be thought as the tiling energy). Fixed-points of such a process play the role of quasicrystals. We are here interested in the worst-case expected number of flips to converge towards a fixed-point. Numerical experiments suggest a Θ(n2) bound, where n is the number of tiles of the tiling. We prove a O(n2.5) upper bound and discuss the gap between this bound and the previous one. We also briefly discuss the average-case.
Full Text: PostScript PDF