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

DOI10.1016/J.CRMA.2017.02.011MaRDI QIDQ524867zbMATH OpenOpenAlexFDO

Authors Thomas Budzinski

Publication date 26 April 2017

Published in Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1611.07324

zbMATH Keywords

Markov chainmixing timeuniform triangulation

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Geometric probability and stochastic geometry (60D05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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

Recommendations

• scientific article; zbMATH DE number 1241392
• scientific article; zbMATH DE number 1241390
• Random lattice triangulations: structure and algorithms
• Dynamics of triangulations
• Polynomial mixing time of edge flips on quadrangulations

Cites work

• scientific article; zbMATH DE number 1241390 (Why is no real title available?)
• scientific article; zbMATH DE number 1241392 (Why is no real title available?)
• scientific article; zbMATH DE number 1053457 (Why is no real title available?)
• Bemerkungen zum Vierfarbenproblem
• Compact Brownian surfaces. I: Brownian disks
• Explicit enumeration of triangulations with multiple boundaries
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random lattice triangulations: structure and algorithms
• Scaling limits for the peeling process on random maps
• Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere
• Uniform Infinite Planar Triangulation and Related Time-Reversed Critical Branching Process

Cited in

(5)

• Polynomial mixing time of edge flips on quadrangulations
• Mixing times of Markov chains on 3-orientations of planar triangulations
• scientific article; zbMATH DE number 1241392 (Why is no real title available?)
• Dynamics of triangulations
• scientific article; zbMATH DE number 1241390 (Why is no real title available?)

This page was built for publication: On the mixing time of the flip walk on triangulations of the sphere

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q524867)