Shannon, Lehman, Edmonds, and Matroids
| Speaker: | Ahmad Abdi |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Two
players,
Cut
and
Short,
are
presented
with
a
graph
and
two
distinguished
vertices.
In
his
turn,
Cut
removes
an
edge,
his
object
being
to
disconnect
the
two
vertices.
In
her
alternating
turn,
Short
fixes
an
edge,
making
it
impossible
to
be
removed,
her
object
being
to
connect
the
two
vertices.
This
so-called
switching
game
was
introduced
by
Claude
Shannon
in
1949,
in
an
attempt
to
model
a
breakdown-repair
model
for
graph
connectivity.
He
left
as
an
open
question
whether
a
winning
strategy
exists
for
either
of
the
players.
Alfred
Lehman
in
1964
gave
an
astounding
solution
for
a
more
general
game
played
on
matroids.
His
solution,
however,
did
not
provide
an
efficient
algorithm
to
decide
which
player
had
the
winning
strategy.
This
inspired
Jack
Edmonds
to
come
up
with
many
of
his
amazing
results
on
matroids,
specifically,
the
Matroid
Partitioning
Theorem,
which
fully
answered
Shannon's
question
by
providing
the
long
sought-after
efficient
algorithm.
I
will
give
an
overview
of
these
results,
and
end
with
some
open
questions.