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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that a simple Markov chain, the Glauber dynamics, can efficientlysample independent sets almost uniformly at random in polynomial time forgraphs in a certain class. The class is determined by boundedness of a newgraph parameter called bipartite pathwidth. This result, which we prove for themore general hardcore distribution with fugacity $\lambda$, can be viewed as astrong generalisation of Jerrum and Sinclair's work on approximately countingmatchings, that is, independent sets in line graphs. The class of graphs withbounded bipartite pathwidth includes claw-free graphs, which generalise linegraphs. We consider two further generalisations of claw-free graphs and provethat these classes have bounded bipartite pathwidth. We also show how to extendall our results to polynomially-bounded vertex weights.

Counting independent sets in graphs with bounded bipartite pathwidth