Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
Bordewich, M.; Karpinski, M.; Dyer, M.
Authors
M. Karpinski
M. Dyer
Abstract
We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree ∆ of a vertex and the minimum size m of an edge satisfy m ≥ 2 ∆ + 1. We also show that the Glauber dynamics for proper q-colorings of a hypergraph mixes rapidly if m ≥ 4 and q > ∆, and if m = 3 and q ≥ 1.65 ∆. We give related results on the hardness of exact and approximate counting for both problems.
Citation
Bordewich, M., Karpinski, M., & Dyer, M. (2008). Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Random Structures and Algorithms, 32(3), 375-399. https://doi.org/10.1002/rsa.20204
Journal Article Type | Article |
---|---|
Publication Date | May 1, 2008 |
Deposit Date | Dec 21, 2009 |
Journal | Random Structures and Algorithms |
Print ISSN | 1042-9832 |
Publisher | Wiley |
Peer Reviewed | Peer Reviewed |
Volume | 32 |
Issue | 3 |
Pages | 375-399 |
DOI | https://doi.org/10.1002/rsa.20204 |
Keywords | Path coupling, Markov chain Monte Carlo, Hypergraph coloring, Hypergraph independent set. |
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