The University of Michigan Combinatorics Seminar


Abstract 

Counting matchings in a graph appears frequently in applications: the number of possible matchings of applicants to open positions, the monomerdimer model in statistical mechanics. Such a number can be given as a permanent or a Hafnian of the corresponding 01 matrix; its computation is known to be a ♯Pcomplete 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. 