Matchings, permanents, and their random approximations

Counting matchings in a graph appears frequently in applications: the number of possible matchings of applicants to open positions, the monomer-dimer model in statistical mechanics. Such a number can be given as a permanent or a Hafnian of the corresponding 0-1 matrix; its computation is known to be a ♯P-complete problem. In this talk, for a general public, we discuss some deterministic estimates for permanents, their random approximations, and related quantities for infinite graphs arising in statistical mechanics, if time permits. We will mention a number of open problems.

A variant of this lecture is available online.