# 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.
Keywords :
Type de document :
Communication dans un congrès
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.205-218, 2010, DMTCS Proceedings
Domaine :

Littérature citée [6 références]

https://hal.inria.fr/hal-01185602
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:34:06
Dernière modification le : vendredi 9 mars 2018 - 11:25:00
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:09:57

### Fichier

dmAM0115.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01185602, version 1

### Citation

Thomas Fernique, Damien Regnault. Stochastic Flips on Dimer Tilings. DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.205-218, 2010, DMTCS Proceedings. 〈hal-01185602〉

### Métriques

Consultations de la notice

## 197

Téléchargements de fichiers