Packing T-Joins, Colouring Problems, and Matching Theory
Speaker: | Ahmad Abdi |
---|---|
Affiliation: | University of Waterloo, C & O |
Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
This
is
the
first
and
introductory
talk
of
the
Graph
Theory
Seminar
Series.
In
this
talk,
I
will
try
to
motivate
and
give
an
introduction
to
different
areas
of
graph
theory.
We
will
start
with
a
seemingly
simple,
yet
notoriously
difficult,
problem
stated
as
follows:
given
a
graph
and
an
even
vertex
subset
T,
how
many
pairwise
edge
disjoint
T-joins
can
one
find?
Here,
a
T-join
is
a
subgraph
whose
odd
degree
vertices
are
T.
To
study
this
problem,
we
will
take
a
stroll
along
the
different
areas
of
mathematics.
These
areas
include
graph
minors,
colouring
problems
on
graphs,
matching
theory,
as
well
as
polyhedral
theory.
In
particular,
we
will
discuss
the
four
colour
theorem
and
its
extensions,
Edmonds'
matching
polytope,
as
well
as
Lovasz's
spectacular
result
on
the
so-called
matching
lattice
of
a
graph.