Counting independent sets in unbalanced bipartite graphs
share
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 (Δ_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.
READ FULL TEXT