Counting independent sets and colorings on random regular bipartite graphs

Abstract

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every $\Delta$-regular bipartite graph if $\Delta \ge 53$. In the weighted case, for all sufficiently large integers $\Delta$ and weight parameters $\lambda =\tilde{\Omega }\left(\frac{1}{\Delta }\right)$, we also obtain an FPTAS on almost every $\Delta$-regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all $q\ge 3$ and sufficiently large integers $\Delta =\Delta (q)$, there is an FPTAS to count the number of $q$-colorings on almost every $\Delta$-regular bipartite graph.