Title: The flip Markov chain for connected regular graphs,
Abstract: 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 $2r$-regular graphs with $n$
vertices, where $n\geq 8$ and $r = r(n)\geq 2$. Formally, we prove that the
distribution of the flip chain will be within $\varepsilon$ of uniform in total
variation distance after $\text{poly}(n,r,\log(\varepsilon^{-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.