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.

Graphs and Matroids Seminar - Catherine GreenhillExport this event to calendar

Wednesday, June 5, 2019 — 3:30 PM EDT

Title: Approximately counting independent sets in graphs with bounded bipartite pathwidth

Speaker: Catherine Greenhill
Affiliation: University of New South Wales
Room: MC 5479

Abstract:

In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting
matchings in a given graph G is rapidly mixing. This chain can equivalently
be viewed as counting independent sets in line graphs. We generalise their
approach to the class of all graphs with the following property: every bipartite
induced subgraph of G has pathwidth at most p. Here p is a positive integer
and the mixing time of the Markov chain will depend on p.
We also describe two classes of graphs (described in terms of forbidden induced
subgraphs) that satisfy this condition. Both of these classes generalise the class
of claw-free graphs.

Location 
MC - Mathematics & Computer Building
5479
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. 2021 (75)
    1. August (6)
    2. July (10)
    3. June (12)
    4. May (7)
    5. April (9)
    6. March (13)
    7. February (8)
    8. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)