Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs (Q2213805)

Summary: 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.