Switch-Based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
| Authors |
|
|---|---|
| Publication date | 13-11-2020 |
| Journal | The Electronic Journal of Combinatorics |
| Article number | P4.29 |
| Volume | Issue number | 27 | 4 |
| Number of pages | 25 |
| Organisations |
|
| Abstract | We consider the irreducibility of switch-based Markov chains for the approximate uniform sampling of Hamiltonian cycles in a given undirected dense graph on n vertices. As our main result, we show that every pair of Hamiltonian cycles in a graph with minimum degree at least n/2+7 can be transformed into each other by switch operations of size at most 10, implying that the switch Markov chain using switches of size at most 10 is irreducible. As a proof of concept, we also show that this Markov chain is rapidly mixing on dense monotone graphs. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.37236/9503 |
| Downloads |
Switch-Based Markov Chains for Sampling Hamiltonian Cycles
(Final published version)
|
| Permalink to this page | |