Abstract: The number of matchings in graphs, appears frequently in applications: the number of possible matchings of applicants to open positions, the monomerdimer model in statistical mechanics. This number can be stated as a permanent or haffnian of the corresponding 0 -1 matrix, which is known to be #P-complete problem. In this talk, for we discuss some deterministic estimates for permanents, their random approximations, and related quantities of infinite graphs arising in statistical mechanics, if time permits. We will mention a number of open problems.

A variant of this lecture is available at http://www2.math.uic.edu/~friedlan/kthectbeam4.8.pdf