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

DOI10.1016/J.CRMA.2017.02.011zbMATH Open1381.60032arXiv1611.07324OpenAlexW2962790450MaRDI QIDQ524867FDOQ524867

Authors: Thomas Budzinski 

Publication date: 26 April 2017

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• Polynomial mixing time of edge flips on quadrangulations
• Mixing times of Markov chains on 3-orientations of planar triangulations
• Title not available (Why is that?)
• Dynamics of triangulations
• Title not available (Why is that?)

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)