Representing some non-representable matroids
Speaker: | Stefan van Zwam |
---|---|
Affiliation: | CWI Amsterdam and University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
A matroid consists of a finite set, together with a partition of its subsets into "dependent" and "independent" ones, subject to some axioms. An important example is a finite set of vectors, where the "independent" subsets are precisely those that are linearly independent.
One
of
the
major
themes
in
matroid
theory
research
is
the
representation
question:
given
a
matroid,
can
we
find
a
dependency-preserving
map
from
the
finite
set
to
a
vector
space?
The
answer
depends
very
much
on
the
(skew)
field
underlying
the
vector
space,
and
many
matroids
are
not
representable
at
all!
Most
research
has
focused
on
matroids
representable
over
a
(commutative)
field.
In
particular,
in
1996,
Semple
and
Whittle
introduced partial
fields to
study
matroids
that
can
be
represented
over
several
distinct
fields.
I
will
start
my
talk
with
an
introduction
to
partial
fields,
and
mention
a
few
applications,
including
a
very
short
proof
of
Tutte's
characterization
of
the
regular
matroids.
The
main
theme
of
this
talk
is skew
partial
fields.
These
generalize
partial
fields
by
dropping
the
requirement
that
multiplication
is
commutative.
The
construction
of
matroid
representations
over
commutative
partial
fields
relies
heavily
on
determinants,
for
which
there
is
no
straightforward
generalization
to
the
noncommutative
case.
To
get
around
this,
we
will
fall
back
on
the
way
Tutte
treated
matroid
representation,
namely
by
something
he
called
a chain
group.
One
feature
of
partial
fields
is
that,
whenever
a
matroid
is
representable
over
a
partial
field,
it
is
also
representable
over
a
field.
Not
so
for
skew
partial
fields:
I
will
exhibit
a
matroid
that
is
representable
over
a
skew
partial
field
but
not
over
any
skew
field!
Hence
skew
partial
fields
provide
a
proper
extension
of
the
notion
of
representability,
while
preserving
most
traditional
properties.
I
will
mention
several
open
problems,
including
one
which
does
not
require
any
matroid
theory
to
solve.
This
talk
is
based
on
joint
work
with
Rudi
Pendavingh.