论文标题
基于开关的马尔可夫链，用于在密集图中采样汉密尔顿周期
Switch-based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
论文作者
论文摘要
我们认为，基于开关的马尔可夫链是在给定的$ N $顶点上给定的无向密度图中对哈密顿周期进行近似均匀采样的不可约性。作为我们的主要结果，我们表明，每对汉密尔顿周期至少至少$ n/2+7 $，可以通过大小最多$ 10 $的开关操作将彼此转换为彼此，这意味着使用最多$ 10 $的开关Markov链条是不可记录的。作为概念的证明，我们还表明，该马尔可夫链正在迅速在密集的单调图上混合。
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.
