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.
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
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

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

Collections

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〉

Partager

Métriques

Consultations de la notice

191

Téléchargements de fichiers

124