Counting Independent Sets and Colorings on Random Regular Bipartite Graphs

摘要

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 = 53. In the weighted case, for all sufficiently large integers Delta and weight parameters lambda = Omega~ (1/(Delta)), 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 = 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.