Extremal hpergraphs for packing and covering
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5158|
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ó.
200 University Avenue West
Waterloo, ON N2L 3G1