University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Shmuel FriedlandExport this event to calendar

Friday, November 20, 2009 — 3:30 PM to 4:30 PM EST

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).

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2020 (33)
    1. March (11)
    2. February (11)
    3. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)