Friday, March 18, 2016 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: Recognizing frame matroids
Speaker: | Jim Geelen |
Affiliation: | University of Waterloo |
Room: | MC 5501 |
Abstract:
A
{\em
frame}
matrix
is
one
that
has
at
most
two
nonzero
entries
in
each
column.
In
joint
work
with
Rong
Chen,
Benson
Joeris,
and
Peter
Nelson
we
give
a
polynomial-time
algorithm
for
the
problem
of
deciding
whether
a
given
matrix
is
row-equivalent
to
a
frame
matrix.
For
matrices
over
the
two
element
field
this
problem
is
equivalent
to
the
problem
of
recognizing
whether
a
given
binary
matroid
is
graphic,
which
was
solved
by
Tutte
in
1960.
In
the
talk
I
will
discuss
the
motivation
for
the
problem
and
give
an
overview
of
the
algorithm.
No
prior
exposure
to
matroid
theory
is
assumed.