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