2020/11/19 by Pieter Kleer, Kleer, Pieter, Viresh Patel +3
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2011.09726
openalex publication_date 2020/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the irreducibility of switch-based Markov chains for the\napproximate uniform sampling of Hamiltonian cycles in a given undirected dense\ngraph on n vertices. As our main result, we show that every pair of\nHamiltonian cycles in a graph with minimum degree at least n/2+7 can be\ntransformed into each other by switch operations of size at most 10, implying\nthat the switch Markov chain using switches of size at most 10 is\nirreducible. As a proof of concept, we also show that this Markov chain is\nrapidly mixing on dense monotone graphs.\n