Dynamics of lattice triangulations on thin rectangles

Pietro Caputo, Fabio Martinelli, Alistair Sinclair, Alexandre Stauffer

Research output: Contribution to journalArticle

4 Citations (Scopus)
78 Downloads (Pure)

Abstract

We consider random lattice triangulations of $n\times k$ rectangular regions with weight $\lambda^{|\sigma|}$ where $\lambda>0$ is a parameter and $|\sigma|$ denotes the total edge length of the triangulation. When $\lambda\in(0,1)$ and $k$ is fixed, we prove a tight upper bound of order $n^2$ for the mixing time of the edge-flip Glauber dynamics. Combined with the previously known lower bound of order $\exp(\Omega(n^2))$ for $\lambda>1$ [3], this establishes the existence of a dynamical phase transition for thin rectangles with critical point at $\lambda=1$.
Original languageEnglish
Pages (from-to)1-22
JournalElectronic Journal of Probability
Volume21
DOIs
Publication statusPublished - 14 Apr 2016

Fingerprint

Rectangle
Triangulation
Dynamical Phase Transition
Glauber Dynamics
Mixing Time
Flip
Critical point
Lower bound
Upper bound
Denote
Lower bounds
Phase transition

Keywords

  • math.PR
  • cs.DM
  • math.CO

Cite this

Dynamics of lattice triangulations on thin rectangles. / Caputo, Pietro; Martinelli, Fabio; Sinclair, Alistair; Stauffer, Alexandre.

In: Electronic Journal of Probability, Vol. 21, 14.04.2016, p. 1-22.

Research output: Contribution to journalArticle

Caputo, Pietro ; Martinelli, Fabio ; Sinclair, Alistair ; Stauffer, Alexandre. / Dynamics of lattice triangulations on thin rectangles. In: Electronic Journal of Probability. 2016 ; Vol. 21. pp. 1-22.
@article{a21c151769414382940b25b56c6f4bf4,
title = "Dynamics of lattice triangulations on thin rectangles",
abstract = "We consider random lattice triangulations of $n\times k$ rectangular regions with weight $\lambda^{|\sigma|}$ where $\lambda>0$ is a parameter and $|\sigma|$ denotes the total edge length of the triangulation. When $\lambda\in(0,1)$ and $k$ is fixed, we prove a tight upper bound of order $n^2$ for the mixing time of the edge-flip Glauber dynamics. Combined with the previously known lower bound of order $\exp(\Omega(n^2))$ for $\lambda>1$ [3], this establishes the existence of a dynamical phase transition for thin rectangles with critical point at $\lambda=1$.",
keywords = "math.PR, cs.DM, math.CO",
author = "Pietro Caputo and Fabio Martinelli and Alistair Sinclair and Alexandre Stauffer",
year = "2016",
month = "4",
day = "14",
doi = "10.1214/16-EJP4321",
language = "English",
volume = "21",
pages = "1--22",
journal = "Electronic Journal of Probability",
issn = "1083-6489",
publisher = "Institute of Mathematical Statistics",

}

TY - JOUR

T1 - Dynamics of lattice triangulations on thin rectangles

AU - Caputo, Pietro

AU - Martinelli, Fabio

AU - Sinclair, Alistair

AU - Stauffer, Alexandre

PY - 2016/4/14

Y1 - 2016/4/14

N2 - We consider random lattice triangulations of $n\times k$ rectangular regions with weight $\lambda^{|\sigma|}$ where $\lambda>0$ is a parameter and $|\sigma|$ denotes the total edge length of the triangulation. When $\lambda\in(0,1)$ and $k$ is fixed, we prove a tight upper bound of order $n^2$ for the mixing time of the edge-flip Glauber dynamics. Combined with the previously known lower bound of order $\exp(\Omega(n^2))$ for $\lambda>1$ [3], this establishes the existence of a dynamical phase transition for thin rectangles with critical point at $\lambda=1$.

AB - We consider random lattice triangulations of $n\times k$ rectangular regions with weight $\lambda^{|\sigma|}$ where $\lambda>0$ is a parameter and $|\sigma|$ denotes the total edge length of the triangulation. When $\lambda\in(0,1)$ and $k$ is fixed, we prove a tight upper bound of order $n^2$ for the mixing time of the edge-flip Glauber dynamics. Combined with the previously known lower bound of order $\exp(\Omega(n^2))$ for $\lambda>1$ [3], this establishes the existence of a dynamical phase transition for thin rectangles with critical point at $\lambda=1$.

KW - math.PR

KW - cs.DM

KW - math.CO

UR - http://dx.doi.org/10.1214/16-EJP4321

UR - http://dx.doi.org/10.1214/16-EJP4321

U2 - 10.1214/16-EJP4321

DO - 10.1214/16-EJP4321

M3 - Article

VL - 21

SP - 1

EP - 22

JO - Electronic Journal of Probability

JF - Electronic Journal of Probability

SN - 1083-6489

ER -