An FPTAS for the hardcore model on random regular bipartite graphs

摘要

We give a fully polynomial-time approximation scheme (FPTAS) to compute the partition function of the hardcore model of fugacity lambda on random delta-regular bipartite graphs for all sufficiently large delta and lambda >= 4(log delta)(3)/delta. For the special case of lambda = 1, where the partition function computes the number of independent sets, an FPTAS exists for delta >= 50. Our technique is based on the polymer model, which is used by Jenssen, Keevash and Perkins (SODA, 2019) to obtain an FPTAS for #BIS-hard problems for the first time. The technique also applies to counting q-colorings: For q >= 3 and delta >= delta(q), there is an FPTAS to compute the number of q-colorings on random delta-regular bipartite graphs.

关键词