Counting independent sets in unbalanced bipartite graphs

2019/06/04 by Cannon, Sarah, Perkins, Will · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1906.01666

Abstract

We give an FPTAS for approximating the partition function of the hard-core model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the sides (L,R) of the bipartition. This includes, among others, the biregular case when λ=1 (approximating the number of independent sets of G) and Δ_R ≥ 7Δ_L log(Δ_L). Our approximation algorithm is based on truncating the cluster expansion of a polymer model partition function that expresses the hard-core partition function in terms of deviations from independent sets that are empty on one side of the bipartition. As a consequence of the method, we also prove that the hard-core model on such graphs exhibits exponential decay of correlations by utilizing connections between the cluster expansion and joint cumulants.

Cited by

• Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence

Related

• Approximately counting independent sets in bipartite graphs via graph containers
• Counting independent sets in expanding bipartite regular graphs
• Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
• Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
• A refined graph container lemma and applications to the hard-core model on bipartite expanders