Photo from wikipedia
An edge flipping is a non-reversible Markov chain on a given connected graph, as defined in Chung and Graham (2012). In the same paper, edge flipping eigenvalues and stationary distributions… Click to show full abstract
An edge flipping is a non-reversible Markov chain on a given connected graph, as defined in Chung and Graham (2012). In the same paper, edge flipping eigenvalues and stationary distributions for some classes of graphs were identified. We further study edge flipping spectral properties to show a lower bound for the rate of convergence in the case of regular graphs. Moreover, we show by a coupling argument that a cutoff occurs at $\frac{1}{4} n \log n$ for the edge flipping on the complete graph.
Keywords:
mixing time;
regular graphs;
edge flipping;
time bounds
Journal Title: Journal of Applied Probability
Year Published: 2022
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Journal of Applied Probability
Year Published: 2022
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!