Yunus Emre Demirci, Ümit Işlak, Alperen Özdemir
Published 2022-08-31Version 1
The edge flipping is a non-reversible Markov chain on a given connected graph, which is defined by Chung and Graham. 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 1/4 n log n for the edge flipping on the complete graph by a coupling argument
Comments: 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. arXiv admin note: substantial text overlap with arXiv:2201.03315
Mixing time bounds for edge flipping on regular graphs
New Lower Bounds for Trace Reconstruction
Exact upper and lower bounds on the difference between the arithmetic and geometric means
![QR code for arXiv:2208.14618 [math.PR]](http://oss.arxitics.com/images/favicon.svg)