Counting perfect matchings in dense regular bipartite graphs
Freddie Manners (UCSD)
Monday, June 1 2026, 2-3pm
Abstract:
Given a d-regular bipartite graph, how many perfect matchings does it have? Equivalently, what is the permanent of the corresponding 0-1 matrix? It is well-known that the answer is at least 1, and known that it is #P-hard to compute exactly. Some general upper and lower bounds have been proven, but they are typically quite far apart. In this talk we describe an asymptotic formula for the number of perfect matchings, up to a factor 1+o(1), depending only on the singular values of the graph. The formula applies to all somewhat dense graphs under a mild (and necessary) hypothesis that they are not "almost disconnected". We will outline some consequences, and the key ideas of the proof. Joint work with Emily Zhu.