Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.dam.2018.06.019 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Markov chain,Graph,Connected graph,Regular graph | Total variation,Graph,Discrete mathematics,Combinatorics,Flip,Polynomial,Vertex (geometry),Upper and lower bounds,Markov chain,Uniform distribution (continuous),Mathematics | Journal |
Volume | ISSN | Citations |
254 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 287 | 30.73 |
| Martin E. Dyer | 2 | 529 | 116.66 |
| Catherine Greenhill | 3 | 628 | 62.40 |
| Andrew J. Handley | 4 | 11 | 1.41 |