On the mixing time of the flip walk on triangulations of the sphere

Thomas Budzinski

doi:10.1016/j.crma.2017.02.011

Probability theory

On the mixing time of the flip walk on triangulations of the sphere
[Flips sur les triangulations de la sphère : une borne inférieure pour le temps de mélange]

Présenté par : Jean-François Le Gall

Thomas Budzinski ¹

¹ ENS Paris and Université Paris-Saclay, France

Comptes Rendus. Mathématique, Volume 355 (2017) no. 4, pp. 464-471.

Résumé
Abstract

Un moyen simple de simuler une triangulation uniforme de la sphère avec un nombre fixé n de sommets est d'utiliser une méthode de Monte-Carlo : on démarre avec une triangulation quelconque, puis, de manière répétée, on choisit une arête uniformément et on la « flippe », i.e. on l'efface et on la remplace par l'autre diagonale du quadrilatère qui se forme. Nous montrons que le temps de mélange de la chaîne de Markov obtenue est au moins d'ordre $n^{5 / 4}$ .

A simple way to sample a uniform triangulation of the sphere with a fixed number n of vertices is the Monte-Carlo method: we start from an arbitrary triangulation and flip repeatedly a uniformly chosen edge. We give a lower bound of order $n^{5 / 4}$ on the mixing time of this Markov chain.

Reçu le : 2016-11-29
Accepté le : 2017-02-27
Publié le : 2017-03-13

DOI : 10.1016/j.crma.2017.02.011

Affiliations des auteurs :

Thomas Budzinski ¹

¹ ENS Paris and Université Paris-Saclay, France

@article{CRMATH_2017__355_4_464_0,
     author = {Thomas Budzinski},
     title = {On the mixing time of the flip walk on triangulations of the sphere},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {464--471},
     publisher = {Elsevier},
     volume = {355},
     number = {4},
     year = {2017},
     doi = {10.1016/j.crma.2017.02.011},
     language = {en},
}

TY  - JOUR
AU  - Thomas Budzinski
TI  - On the mixing time of the flip walk on triangulations of the sphere
JO  - Comptes Rendus. Mathématique
PY  - 2017
SP  - 464
EP  - 471
VL  - 355
IS  - 4
PB  - Elsevier
DO  - 10.1016/j.crma.2017.02.011
LA  - en
ID  - CRMATH_2017__355_4_464_0
ER  -

%0 Journal Article
%A Thomas Budzinski
%T On the mixing time of the flip walk on triangulations of the sphere
%J Comptes Rendus. Mathématique
%D 2017
%P 464-471
%V 355
%N 4
%I Elsevier
%R 10.1016/j.crma.2017.02.011
%G en
%F CRMATH_2017__355_4_464_0

Thomas Budzinski. On the mixing time of the flip walk on triangulations of the sphere. Comptes Rendus. Mathématique, Volume 355 (2017) no. 4, pp. 464-471. doi : 10.1016/j.crma.2017.02.011. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2017.02.011/

Bibliographie
Cité par

[1] J. Bettinelli; G. Miermont Compact Brownian surfaces I. Brownian disks, 2015 | arXiv

[2] T. Budzinski The hyperbolic Brownian plane, Apr. 2016 | arXiv

[3] P. Caputo; F. Martinelli; A. Sinclair; A. Stauffer Random lattice triangulations: structure and algorithms, Ann. Appl. Probab., Volume 25 (2015) no. 3, pp. 1650-1685

[4] N. Curien; J.-F. Le Gall First-passage percolation and local perturbations on random planar maps, 2015 | arXiv

[5] N. Curien; J.-F. Le Gall Scaling limits for the peeling process on random maps, Ann. Inst. Henri Poincaré Probab. Stat., Volume 53 (2017) no. 1, pp. 322-357 | DOI

[6] J. Jurkiewicz; A. Krzywicki; B. Petersson A numerical study of discrete euclidean Polyakov surfaces, Phys. Lett. B, Volume 168 (1986) no. 3, pp. 273-278

[7] V. Kazakov; I. Kostov; A. Migdal Critical properties of randomly triangulated planar random surfaces, Phys. Lett. B, Volume 157 (1985) no. 4, pp. 295-300

[8] H. Komuro The diagonal flips of triangulations on the sphere, Yokohama Math. J., Volume 44 (1997) no. 2, pp. 115-122

[9] M. Krikun A uniformly distributed infinite planar triangulation and a related branching process, Zap. Nauč. Semin. POMI (Teor. Predst. Din. Sist. Komb. i Algoritm. Metody), Volume 307 (2004) no. 10, pp. 141-174 (282–283)

[10] M. Krikun Explicit enumeration of triangulations with multiple boundaries, Electron. J. Comb., Volume 14 (2007) no. 1 Research Paper 61, 14 pp. (electronic)

[11] J.-F. Le Gall; F. Paulin Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere, Geom. Funct. Anal., Volume 18 (2008) no. 3, pp. 893-918

[12] D.A. Levin; Y. Peres; E.L. Wilmer Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, USA, 2009

[13] L. McShine; P. Tetali On the mixing time of the triangulation walk and other Catalan structures, Princeton, NJ, USA, December 12–14, 1997 (1997), pp. 147-160

[14] M.S. Molloy; B. Reed; W. Steiger On the mixing rate of the triangulation walk, DIMACS Ser. Discret. Math. Theor. Comput. Sci., vol. 43, 1998, pp. 179-190

[15] K. Wagner Bemerkungen zum Vierfarbenproblem, Jahresber. Dtsch. Math.-Ver., Volume 46 (1936), pp. 26-32

Cité par Sources :

Commentaires - Politique