Graphs and Matroids Seminar - Catherine Greenhill

Wednesday, June 5, 2019 3:30 pm - 3:30 pm EDT (GMT -04:00)

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

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


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.