Counting independent sets and colorings on random regular bipartite graphs
share
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every Δ-regular bipartite graph if Δ> 53. In the weighted case, for all sufficiently large integers Δ and weight parameters λ=Ω̃(1/Δ), we also obtain an FPTAS on almost every Δ-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 Δ=Δ(q), there is an FPTAS to count the number of q-colorings on almost every Δ-regular bipartite graph.
READ FULL TEXT