# 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. Posted on Categories Articles