co.combinatorics – Relationship between minimum vertex cover and matching width


Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $tau(H)$ (i.e. $tau(H)=min{|Q|: Qsubseteq V(H), ecap Qneq emptyset text{ for all } ein E(H)}$).

Question: Is $tau(H)$ at most 3 times the matching width of $H$?

Given a matching $M$ in $H$, let $rho(M)$ be the minimum size of a set of edges $F$ having the property that every edge in $M$ intersects some edge in $F$. Let the matching width of $H$, denoted $mathrm{mw}(H)$, be the maximum value of $rho(M)$ over all matchings $M$ in $H$.

The question is motivated by Aharoni’s proof of Ryser’s conjecture for 3-partite 3-uniform hypergraphs Aharoni, Ron, Ryser’s conjecture for tripartite 3-graphs, Combinatorica 21, No. 1, 1-4 (2001). ZBL1107.05307. where he uses the fact that $tau(H)leq 2mathrm{mw}(H)$ for 2-partite 2-uniform hypergraphs $H$.

I suspect that my question has a negative answer. If the answer is positive, this would imply Ryser’s conjecture is true for 4-partite 4-uniform hypergraphs; so in this case the answer is likely very difficult.