{
  "id": "2001.04166",
  "version": "v1",
  "published": "2020-01-13T11:27:39.000Z",
  "updated": "2020-01-13T11:27:39.000Z",
  "title": "A polynomial upper bound for the mixing time of edge rotations on planar maps",
  "authors": [
    "Alessandra Caraceni"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We consider a natural local dynamic on the set of all rooted planar maps with $n$ edges that is in some sense analogous to \"edge flip\" Markov chains, which have been considered before on a variety of combinatorial structures (triangulations of the $n$-gon and quadrangulations of the sphere, among others). We provide the first polynomial upper bound for the mixing time of this \"edge rotation\" chain on planar maps: we show that the spectral gap of the edge rotation chain is bounded below by an appropriate constant times $n^{-11/2}$. In doing so, we provide a partially new proof of the fact that the same bound applies to the spectral gap of edge flips on quadrangulations, which makes it possible to generalise a recent result of the author and Stauffer to a chain that relates to edge rotations via Tutte's bijection.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-01-13T11:27:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J10"
    ],
    "keywords": [
      "mixing time",
      "first polynomial upper bound",
      "edge flip",
      "spectral gap",
      "appropriate constant times"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}