Date & Time: Thursday, December 24, 2009, 16:30-17:30.
Venue: Ramanujan Hall

Title: Matchings, permanents and their random approximations

Speaker: Shmuel Friedland, University of Illinois, Chicago

Abstract: The number of matchings in graphs, appears frequently in applications: the number of possible matchings of applicants to open positions, the monomer- dimer model in statistical mechanics. This number can be stated as a per- manent or haffnian of the corresponding 0 − 1 matrix, which is known to be #P -complete problem. In this talk, for we discuss some deterministic esti- mates 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. .

Another interesting finding is that residual empirical process tests in the scale problem are robust against not knowing the scale parameter.

The third finding is that in linear regression models with a non-zero intercept parameter the first order difference between the empirical d.f. of residuals and the null d.f. can not be used to fit an error d.f.

This talk is based on ongoing joint work with Donatas Surgailis.