Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width
Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width
复制标题
DOI：
10.37236/4195
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
M. Bordewich;Ross J. Kang
中科院分区：
文献类型：
--
作者：
M. Bordewich;Ross J. Kang
受铁磁伊辛模型的“子图世界”观点的启发，我们基于图、超图和拟阵多项式类的子集展开表达式分析了Glauber动力学的混合时间。一个典型的路径参数，我们证明了在这个框架内定义的链混合迅速图，超图和拟阵的有界树宽度。这推广了Tutte多项式、邻接秩（$R_2$-）多项式和交错多项式的快速混合的已知结果。特别是Glauber动力学的$R_2$-多项式是已知的混合迅速的树，这导致了希望快速混合更广泛的一类图。我们表明，Glauber动态的一个非常广泛的一类多项式混合迅速有界树宽度的图形，包括许多情况下，在其中的Glauber动态不迅速混合所有的图形。这表明树或有界树宽图上的快速混合并不能为所有图上的快速混合提供强有力的证据。
Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width. This extends known results on rapid mixing for the Tutte polynomial, adjacency-rank ($R_2$-)polynomial and interlace polynomial. In particular Glauber dynamics for the $R_2$-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.