Switch-Based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
Switch-Based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
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 …