|
Friday, April 5, 2013 |
|
|
|
|
Extremal hypergraphs for packing and covering |
|
|
A {\it packing} (or {\it matching}) in a hypergraph $H$ is a set of
pairwisedisjoint edges of $H$. A {\it 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)$ enotes 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. |