Ryser's conjecture for multipartite hypergraphs

Ian Wanless
Monash University

PDF

Minisymposium: COMBINATORICS

Content: An {\em $r$-partite hypergraph} has a partition of the vertices into disjoint sets $V_1,\dots,V_r$ and every edge includes exactly one vertex from each $V_i$. A {\em matching} in a hypergraph $H$ is a set of disjoint edges. The largest size of a matching in $H$ is denoted $\nu(H)$. A {\em cover} in a hypergraph is a set of vertices which meets every edge. The size of the largest cover in $H$ is denoted $\tau(H)$. Ryser conjectured that $\tau(H)\le(r-1)\nu(H)$ for $r$-partite hypergraphs. Define $f(r)$ to be the smallest number of edges in an $r$-partite hypergraph $H$ with $\nu(H)=1$ and $\tau(H)\ge r-1$ (if such an $H$ exists!). I will discuss work from two recent papers in which we \begin{itemize} \item Prove the special case of Ryser's conjecture where $r\le9$ and $H$ is linear (meaning each pair of edges meets at a unique vertex). \item Disprove a strengthened version of Ryser's conjecture proposed by Aharoni. \item Find the values of $f(6)$ and $f(7)$ and improve the general lower bound on $f(r)$. \end{itemize}

Back to all abstracts