2018/12/07 by Martin J.S. Dyer, Dyer, Martin, Catherine Greenhill +3
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Bayesian Modeling and Causal Inference #Bayesian Methods and Mixture Models
paper · pdf · doi:10.48550/arxiv.1812.03195
We show that a simple Markov chain, the Glauber dynamics, can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity λ, can be viewed as a strong generalisation of Jerrum and Sinclair's work on approximately counting matchings, that is, independent sets in line graphs. The class of graphs with bounded bipartite pathwidth includes claw-free graphs, which generalise line graphs. We consider two further generalisations of claw-free graphs and prove that these classes have bounded bipartite pathwidth. We also show how to extend all our results to polynomially-bounded vertex weights.