Stochastic Flips on Dimer Tilings

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 $\textit{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 $\Theta (n^2)$ bound, where $n$ is the number of tiles of the tiling. We prove a $O(n^{2.5})$ upper bound and discuss the gap between this bound and the previous one. We also briefly discuss the average-case.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185602
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:34:06 PM
Last modification on : Monday, March 4, 2019 - 2:04:14 PM
Long-term archiving on : Wednesday, April 26, 2017 - 10:09:57 AM

File

dmAM0115.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185602, version 1

Collections

Citation

Thomas Fernique, Damien Regnault. Stochastic Flips on Dimer Tilings. pp.205-218. ⟨hal-01185602⟩

Share

Metrics

Record views

208

Files downloads

252