Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width

被引：0

作者：

Bordewich, Magnus ^{[1
]}

Kang, Ross J. ^{[1
]}

机构：

[1] Univ Durham, Durham, England

来源：

AUTOMATA, LANGUAGES AND PROGRAMMING, ICALP, PT I | 2011年 / 6755卷

基金：

英国工程与自然科学研究理事会;

关键词：

Markov chain Monte Carlo; graph polynomials; subset expansion; tree-width; canonical paths; randomised approximation schemes; rapid mixing; MARKOV-CHAINS; TIME; POLYNOMIALS; INVARIANTS; MODELS; NUMBER;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Motivated by the 'subgraphs world' view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs of bounded tree-width. This extends known results on rapid mixing for the Tutte polynomial, the adjacency-rank (R-2-)polynomial and the interlace polynomial.

引用

页码：533 / 544

页数：12

共 46 条

[21] On the tree-depth and tree-width in heterogeneous random graphs
Shang, Yilun
PROCEEDINGS OF THE JAPAN ACADEMY SERIES A-MATHEMATICAL SCIENCES, 2022, 98 (09) : 78 - 83
[22] Maximum likelihood bounded tree-width Markov networks
Srebro, N
ARTIFICIAL INTELLIGENCE, 2003, 143 (01) : 123 - 138
[23] Tree-width and large grid minors in planar graphs
Grigoriev, Alexander
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2011, 13 (01): : 13 - 20
[24] A lower bound on the tree-width of graphs with irrelevant vertices
Adler, Isolde
Krause, Philipp Klaus
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 137 : 126 - 136
[25] Counting truth assignments of formulas of bounded tree-width or clique-width
Fischer, E.
Makowsky, J. A.
Ravve, Ex
DISCRETE APPLIED MATHEMATICS, 2008, 156 (04) : 511 - 529
[26] Learning Bounded Tree-Width Bayesian Networks via Sampling
Nie, Siqi
de Campos, Cassio P.
Ji, Qiang
SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2015, 2015, 9161 : 387 - 396
[27] Rank-width and tree-width of H-minor-free graphs
Fomin, Fedor V.
Oum, Sang-il
Thilikos, Dimitrios M.
EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (07) : 1617 - 1628
[28] Graphs of small rank-width are pivot-minors of graphs of small tree-width
Kwon, O-joung
Oum, Sang-il
DISCRETE APPLIED MATHEMATICS, 2014, 168 : 108 - 118
[29] TREE-WIDTH OF COCOMPARABILITY GRAPHS AND A NEW ORDER THEORETIC PARAMETER
HABIB, M
MOHRING, RH
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1994, 11 (01): : 47 - 60
[30] On the excluded minor structure theorem for graphs of large tree-width
Diestel, Reinhard
Kawarabayashi, Ken-ichi
Mueller, Theodor
Wollan, Paul
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (06) : 1189 - 1210

← 1 2 3 4 5 →