{
  "id": "2201.03315",
  "version": "v2",
  "published": "2022-01-10T12:33:20.000Z",
  "updated": "2022-09-06T15:49:33.000Z",
  "title": "Mixing time bounds for edge flipping on regular graphs",
  "authors": [
    "Yunus Emre Demirci",
    "Ümit Işlak",
    "Alperen Yaşar Özdemir"
  ],
  "comment": "16 pages. An error in the proof of Theorem 1.1 is corrected. The section on vertex flipping is removed. Presentation is revised. Note the change in the title",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The edge flipping is a non-reversible Markov chain on a given connected graph, which is defined by Chung and Graham in [CG12]. In the same paper, its eigenvalues and stationary distributions for some classes of graphs are identified. We further study its spectral properties to show a lower bound for the rate of convergence in the case of regular graphs. Moreover, we show that a cutoff occurs at \\frac{1}{4} n \\log n for the edge flipping on the complete graph by a coupling argument.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-09-06T15:49:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60F05",
      "60G42"
    ],
    "keywords": [
      "mixing time bounds",
      "edge flipping",
      "regular graphs",
      "non-reversible markov chain",
      "stationary distributions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}