Mixing time bounds for edge flipping on regular graphs

Autor:	Yunus Emre Demirci, Ümit Işlak, Alperen Özdemir
Rok vydání:	2023
Předmět:	Statistics and Probability General Mathematics Probability (math.PR) FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) 60C05 60F05 60G42 Statistics Probability and Uncertainty Mathematics - Probability MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	Journal of Applied Probability. :1-16
ISSN:	1475-6072 0021-9002
DOI:	10.1017/jpr.2023.3
Popis:	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. Comment: 17 pages. A correction in the proof of Lemma 3.3 and minor revisions
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::43912cba684f02231079869b83c495a3 https://doi.org/10.1017/jpr.2023.3 Zobrazit plný text záznamu