On packing and covering in hypergraphs

On packing and covering in hypergraphs

Tue, 28/02/2012
14:30 		Penny Haxell (Waterloo) Combinatorial Theory Seminar Add to calendar L3
On packing and covering in hypergraphs
We discuss some recent developments on the following long-standing problem known as Ryser's conjecture. Let $ H $ be an $ r $-partite $ r $-uniform hypergraph. A matching in $ H $ is a set of disjoint edges, and we denote by $ \nu(H) $ the maximum size of a matching in $ H $. A cover of $ H $ is a set of vertices that intersects every edge of $ H $. It is clear that there exists a cover of $ H $ of size at most $ r\nu(H) $, but it is conjectured that there is always a cover of size at most $ (r-1)\nu(H) $.