[HTML][HTML] The flip Markov chain for connected regular graphs

C Cooper, M Dyer, C Greenhill, A Handley - Discrete Applied Mathematics, 2019 - Elsevier
Discrete Applied Mathematics, 2019Elsevier
Mahlmann and Schindelhauer (2005) defined a Markov chain which they called k-Flipper,
and showed that it is irreducible on the set of all connected regular graphs of a given degree
(at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip
chain converges rapidly to the uniform distribution over connected 2 r-regular graphs with n
vertices, where n≥ 8 and r= r (n)≥ 2. Formally, we prove that the distribution of the flip chain
will be within ε of uniform in total variation distance after poly (n, r, log (ε− 1)) steps. This …
Mahlmann and Schindelhauer (2005) defined a Markov chain which they called k-Flipper, and showed that it is irreducible on the set of all connected regular graphs of a given degree (at least 3). We study the 1-Flipper chain, which we call the flip chain, and prove that the flip chain converges rapidly to the uniform distribution over connected 2 r-regular graphs with n vertices, where n≥ 8 and r= r (n)≥ 2. Formally, we prove that the distribution of the flip chain will be within ε of uniform in total variation distance after poly (n, r, log (ε− 1)) steps. This polynomial upper bound on the mixing time is given explicitly, and improves markedly on a previous bound given by Feder et al.(2006). We achieve this improvement by using a direct two-stage canonical path construction, which we define in a general setting. This work has applications to decentralised networks based on random regular connected graphs of even degree, as a self-stabilising protocol in which nodes spontaneously perform random flips in order to repair the network.
Elsevier
顯示最佳搜尋結果。 查看所有結果