Matchings, permanents and their random approximations
| Speaker: | Shmuel Friedland |
|---|---|
| Affiliation: | University of Illinois |
| Room: | Mathematics & Computer Building (MC) 5158 |
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 permanent or haffnian of the corresponding 0-1 matrix, which is known to be #P-complete problem. In this talk, for a general public, 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.
This
lecture
is
dedicated
to
my
colleague
and
collaborator
Uri
N.
Peled.
He
got
his
PhD
from
University
of
Waterloo
1976,
under
the
direction
of
the
late
Peter
L.
Hammer.
Uri
passed
away
after
a
long
battle
with
the
brain
cancer
on
Thursday,
September
3,
2009.
A
variant
of
this
lecture
is
available
as:
Counting
matchings
in
graphs
with
applications
to
the
monomer-dimer
models
(PDF).