Abstract

We obtain FPTAS for counting the number of independent sets and colorings for almost every random d-regular bipartite graph when the degree d is sufficient large (as a function of number of colors q in the case of counting colorings). This extends a recent result by Jenssen, Keevash and Perkins (SODA 2019) and confirms an open question raised there.

Video Recording