Title: Matchings in tripartite hypergraphs
| Speaker: | Penny Haxell |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
A
matching
in
a
hypergraph
is
a
set
of
disjoint
edges.
It
is
a
well-known
difficult
problem
to
give
good
lower
bounds
on
the
maximum
size
of
a
matching
in
a
hypergraph
in
terms
of
other
natural
parameters.
Here
we
focus
on
the
special
case
of
tripartite
hypergraphs:
those
for
which
the
vertex
set
can
be
partitioned
into
three
parts,
such
that
each
edge
contains
exactly
one
vertex
from
each
part.
If
a
tripartite
hypergraph
is
r-regular
(meaning
that
each
vertex
is
in
exactly
r
edges)with
n
vertices
in
each
class
then
it
has
a
matching
of
size
at
least
n/2,
and
this
bound
is
tight
for
certain
special
hypergraphs.
We
investigate
how
the
bound
can
be
improved
for
all
other
hypergraphs.