Title: Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
| Speaker: | Sang-il Oum |
| Affiliation: | Institute for Basic Science / KAIST |
| Zoom: | Join via http://matroidunion.org/?page_id=2477 or please email Shayla Redlin |
Abstract:
Every
minor-closed
class
of
matroids
of
bounded
branch-width
can
be
characterized
by
a
minimal
list
of
excluded
minors,
but
unlike
graphs,
this
list
could
be
infinite
in
general.
However,
for
each
fixed
finite
field
$\mathbb
F$,
the
list
contains
only
finitely
many
$\mathbb
F$-representable
matroids,
due
to
the
well-quasi-ordering
of
$\mathbb
F$-representable
matroids
of
bounded
branch-width
under
taking
matroid
minors
[J.
F.
Geelen,
A.
M.
H.
Gerards,
and
G.
Whittle
(2002)].
But
this
proof
is
non-constructive
and
does
not
provide
any
algorithm
for
computing
these
$\mathbb
F$-representable
excluded
minors
in
general.
We
consider
the
class
of
matroids
of
path-width
at
most
$k$
for
fixed
$k$.
We
prove
that
for
a
finite
field
$\mathbb
F$,
every
$\mathbb
F$-representable
excluded
minor
for
the
class
of
matroids
of
path-width
at
most~$k$
has
at
most
$2^{|\mathbb{F}|^{O(k^2)}}$
elements.
We
can
therefore
compute,
for
any
integer
$k$
and
a
fixed
finite
field
$\mathbb
F$,
the
set
of
$\mathbb
F$-representable
excluded
minors
for
the
class
of
matroids
of
path-width
$k$,
and
this
gives
as
a
corollary
a
polynomial-time
algorithm
for
checking
whether
the
path-width
of
an
$\mathbb
F$-represented
matroid
is
at
most
$k$.
We
also
prove
that
every
excluded
pivot-minor
for
the
class
of
graphs
having
linear
rank-width
at
most
$k$
has
at
most
$2^{2^{O(k^2)}}$
vertices,
which
also
results
in
a
similar
algorithmic
consequence
for
linear
rank-width
of
graphs.
This
is
joint
work
with
Mamadou
M.
Kanté,
Eun
Jung
Kim,
and
O-joung
Kwon.