[Flips sur les triangulations de la sphère : une borne inférieure pour le temps de mélange]
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 .
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 on the mixing time of this Markov chain.
Accepté le :
Publié le :
@article{CRMATH_2017__355_4_464_0,
author = {Budzinski, Thomas},
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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2017.02.011/}
}
TY - JOUR AU - Budzinski, Thomas 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 UR - http://www.numdam.org/articles/10.1016/j.crma.2017.02.011/ DO - 10.1016/j.crma.2017.02.011 LA - en ID - CRMATH_2017__355_4_464_0 ER -
%0 Journal Article %A Budzinski, Thomas %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 %U http://www.numdam.org/articles/10.1016/j.crma.2017.02.011/ %R 10.1016/j.crma.2017.02.011 %G en %F CRMATH_2017__355_4_464_0
Budzinski, Thomas. On the mixing time of the flip walk on triangulations of the sphere. Comptes Rendus. Mathématique, Tome 355 (2017) no. 4, pp. 464-471. doi : 10.1016/j.crma.2017.02.011. http://www.numdam.org/articles/10.1016/j.crma.2017.02.011/
[1] Compact Brownian surfaces I. Brownian disks, 2015 | arXiv
[2] The hyperbolic Brownian plane, Apr. 2016 | arXiv
[3] Random lattice triangulations: structure and algorithms, Ann. Appl. Probab., Volume 25 (2015) no. 3, pp. 1650-1685
[4] First-passage percolation and local perturbations on random planar maps, 2015 | arXiv
[5] 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] A numerical study of discrete euclidean Polyakov surfaces, Phys. Lett. B, Volume 168 (1986) no. 3, pp. 273-278
[7] Critical properties of randomly triangulated planar random surfaces, Phys. Lett. B, Volume 157 (1985) no. 4, pp. 295-300
[8] The diagonal flips of triangulations on the sphere, Yokohama Math. J., Volume 44 (1997) no. 2, pp. 115-122
[9] 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] Explicit enumeration of triangulations with multiple boundaries, Electron. J. Comb., Volume 14 (2007) no. 1 Research Paper 61, 14 pp. (electronic)
[11] Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere, Geom. Funct. Anal., Volume 18 (2008) no. 3, pp. 893-918
[12] Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, USA, 2009
[13] On the mixing time of the triangulation walk and other Catalan structures, Princeton, NJ, USA, December 12–14, 1997 (1997), pp. 147-160
[14] On the mixing rate of the triangulation walk, DIMACS Ser. Discret. Math. Theor. Comput. Sci., vol. 43, 1998, pp. 179-190
[15] Bemerkungen zum Vierfarbenproblem, Jahresber. Dtsch. Math.-Ver., Volume 46 (1936), pp. 26-32
Cité par Sources :
