Seminar series
Date
Tue, 28 Feb 2012
Time
14:30 -
15:30
Location
L3
Speaker
Penny Haxell (Waterloo)
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)$.