Mixing time bounds for edge flipping on regular graphs

2022/01/10 by Demirci, Yunus Emre, Işlak, Ümit, Özdemir, Alperen Yaşar
#60C05 #60F05 #60G42 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2201.03315

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 (1)/(4) n log n for the edge flipping on the complete graph by a coupling argument.

Related

• Mixing time bounds for edge flipping on regular graphs
• Polynomial mixing time of edge flips on quadrangulations
• The flip Markov chain for connected regular graphs
• Analysis of a non-reversible Markov chain speedup by a single edge
• A polynomial bound on the mixing time of a Markov chain for sampling\n regular directed graphs