Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width
Bordewich, M.; Kang, R.
Authors
R. Kang
Abstract
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 dened 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 (R2-)polynomial and interlace polynomial. In particular Glauber dynamics for the R2-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 oer strong evidence towards rapid mixing on all graphs.
Citation
Bordewich, M., & Kang, R. (2014). Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width. Electronic Journal of Combinatorics, 21(4), Article 19
Journal Article Type | Article |
---|---|
Publication Date | Oct 23, 2014 |
Deposit Date | Apr 28, 2015 |
Publicly Available Date | Mar 29, 2024 |
Journal | Electronic Journal of Combinatorics |
Publisher | Electronic Journal of Combinatorics |
Peer Reviewed | Peer Reviewed |
Volume | 21 |
Issue | 4 |
Article Number | 19 |
Keywords | Markov chain Monte Carlo, Graph polynomials, Tree-width, Canonical paths, Approximate counting. |
Publisher URL | http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19/pdf |
Files
Published Journal Article
(419 Kb)
PDF
You might also like
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search