King's College London

Research portal

The flip Markov chain for connected regular graphs

Research output: Contribution to journalArticle

Colin Cooper, Martin Dyer, Catherine Greenhill, Andrew Handley

Original languageEnglish
JournalDISCRETE APPLIED MATHEMATICS
Early online date4 Jul 2018
DOIs
StateE-pub ahead of print - 4 Jul 2018

Links

King's Authors

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≥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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454