Friday, April 5, 2013 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Extremal hpergraphs for packing and covering
| Speaker: | Penny Haxell |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
A
packing (or
matching)
in
a
hypergraph
H is
a
set
of
pairwisedisjoint
edges
of
H.
A
cover
of
H is
a
set
C of
vertices
that
meets
all
edges
of
H.
A
famous
open
problem
known
as
Ryser's
Conjecture
states
that
any
r-partite
r-uniform
hypergraph
should
have
a
cover
of
size
at
most
$(r-1)\nu(H)$,
where
$\nu(H)$
denotes
the
size
of
a
largest
packing
in
H.
This
was
proved
by
Aharoni
in
2001
for
the
case
r=3.
Here
we
show
that
if
equality
holds
in
this
case
then
H belongs
to
a
special
class
of
hypergraphs
we
call
"home
base
hypergraphs''.
To
prove
this
we
need
to
establish
some
auxiliary
results
on
connectedness
of
the
matching
complex
of
bipartite
graphs.
Joint
work
with
L.
Narins
and
T.
Szabó.