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 on random Δ-regular bipartite graphs for all sufficiently large Δ and . For the special case of , where the partition function computes the number of independent sets, an FPTAS exists for . 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 -colorings: For and , there is an FPTAS to compute the number of -colorings on random Δ-regular bipartite graphs.