Thomas Fernique ; Damien Regnault - Stochastic Flips on Dimer Tilings

dmtcs:2803 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2803
Stochastic Flips on Dimer TilingsConference paper

Authors: Thomas Fernique 1; Damien Regnault ORCID1

  • 1 Laboratoire d'informatique Fondamentale de Marseille

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.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Complexity,Dimer tiling,Flip,Markov chain,Quasicrystal,Stopping time,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

2 Documents citing this article

Consultation statistics

This page has been seen 275 times.
This article's PDF has been downloaded 257 times.