English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We give a new rapid mixing result for a natural random walk on theindependent sets of a graph $G$. We show that when $G$ has bounded treewidth,this random walk -- known as the Glauber dynamics for the hardcore model --mixes rapidly for all fixed values of the standard parameter $\lambda > 0$,giving a simple alternative to existing sampling algorithms for thesestructures. We also show rapid mixing for analogous Markov chains on dominatingsets, $b$-edge covers, $b$-matchings, maximal independent sets, and maximal$b$-matchings. (For $b$-matchings, maximal independent sets, and maximal$b$-matchings we also require bounded degree.) Our results imply simpleralternatives to known algorithms for the sampling and approximate countingproblems in these graphs. We prove our results by applying a divide-and-conquerframework we developed in a previous paper, as an alternative to theprojection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda.We extend this prior framework to handle chains for which the application ofthat framework is not straightforward, strengthening existing results by Dyer,Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on $q$-coloringsof graphs of bounded treewidth and bounded degree.

Rapid mixing for the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs