Polynomial mixing time of edge flips on quadrangulations

DOI10.1007/S00440-019-00913-5MaRDI QIDQ2291687zbMATH OpenOpenAlexFDO

Authors Alessandra Caraceni, Alexandre Stauffer

Publication date 31 January 2020

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Catalan structuresmixing timequadrangulations with \(n\) faces

Mathematics Subject Classification ID

Combinatorial probability (60C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We establish the first polynomial upper bound for the mixing time of random edge flips on rooted quadrangulations: we show that the spectral gap of the edge flip Markov chain on quadrangulations with $n$ faces admits, up to constants, an upper bound of $n^{-5/4}$ and a lower bound of $n^{-11/2}$. In order to obtain the lower bound, we also consider a very natural Markov chain on plane trees (or, equivalently, on Dyck paths) and improve the previous lower bound for its spectral gap obtained by Shor and Movassagh.

Review text

The paper considers the spectral gap \(\nu _n\) of the edge flip Markov chain on quadrangulations with \(n\) faces and gets a polynomial upper and lower bound on its mixing time. It shows that for \(\nu _n\) the inequality \[ C_1n^{-11/2}\le \nu _n\le C_2n^{-5/4} \] holds, where \(C_1\) and \(C_2\) are positive constants independent of \(n\).

Recommendations

• A polynomial upper bound for the mixing time of edge rotations on planar maps
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
• On the mixing time of the flip walk on triangulations of the sphere
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
• scientific article; zbMATH DE number 1241392

Cites work

• A Lyapunov function for Glauber dynamics on lattice triangulations
• A view from infinity of the uniform infinite planar quadrangulation
• Comparison theorems for reversible Markov chains
• Dynamics of lattice triangulations on thin rectangles
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• 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 1750693 (Why is no real title available?)
• Logarithmic Sobolev inequalities for finite Markov chains
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing Time for a Markov Chain on Cladograms
• Mixing times of lozenge tiling and card shuffling Markov chains
• On the mixing time of the flip walk on triangulations of the sphere
• Phase transitions in random dyadic tilings and rectangular dissections
• Planar Maps are Well Labeled Trees
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
• Random lattice triangulations: structure and algorithms
• Simple random walk on the uniform infinite planar quadrangulation: Subdiffusivity via pioneer points
• Supercritical entanglement in local systems: counterexample to the area law for quantum matter
• The Aldous chain on cladograms in the diffusion limit
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• The gap of Fredkin quantum spin chain is polynomially small
• The two uniform infinite quadrangulations of the plane have the same law
• Triangulating the Circle, at Random
• Uniform control of local times of spectrally positive stable processes
• Uniqueness and universality of the Brownian map

Cited in

(10)

• A polynomial upper bound for the mixing time of edge rotations on planar maps
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
• On the mixing time of the flip walk on triangulations of the sphere
• Growing uniform planar maps face by face
• Mixing time bounds for edge flipping on regular graphs
• What is a random surface?
• On the mixing time of the face flip- and up/down Markov chain for some families of graphs
• Where do (random) trees grow leaves?
• Rapid mixing of the flip chain over non-crossing spanning trees

This page was built for publication: Polynomial mixing time of edge flips on quadrangulations

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