Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Path coupling using stopping times
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
Authors
Martin Dyer
Marek Karpinski
Contributors
Maciej Liśkiewicz
Editor
Rüdiger Reischuk
Editor
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 state results that the Glauber dynamics for proper q-colourings 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., Dyer, M., & Karpinski, M. (2005, August). Path coupling using stopping times. Presented at 15th International Symposium Fundamentals of Computation Theory : FCT 2005., Lubeck, Germany
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 15th International Symposium Fundamentals of Computation Theory : FCT 2005. |
Start Date | Aug 17, 2005 |
End Date | Aug 20, 2005 |
Publication Date | Aug 1, 2005 |
Deposit Date | Oct 30, 2008 |
Print ISSN | 0302-9743 |
Pages | 19-31 |
Series Title | Lecture notes in computer science |
Series Number | 3623 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Fundamentals of computation theory : 15th International Symposium, FCT 2005, 17-20 August 2005, Lübeck, Germany ; proceedings. |
DOI | https://doi.org/10.1007/11537311_3 |
Keywords | Hypergraph, Graph colouring, Independent set. |
Public URL | https://durham-repository.worktribe.com/output/1162423 |
Additional Information | 17-20 August 2005 |
You might also like
Quantifying the difference between phylogenetic diversity and diversity indices
(2024)
Journal Article
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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