Let $H$ be a 3-partite 3-uniform hypergraph with minimum vertex cover number $\tau(H)$ (i.e. $\tau(H)=\min\{|Q|: Q\subseteq V(H), e\cap Q\neq \emptyset \text{ for all } e\in 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$ in $H$ having the property that every edge in $M$ intersects some edge in $F$. The *matching width* of $H$, denoted $\mathrm{mw}(H)$, is the maximum value of $\rho(M)$ over all matchings $M$ in $H$. For example, let $H$ be a 3-uniform hypergraph consisting of four edges $e\_1, e\_2, e\_3, f$ where $e\_1, e\_2, e\_3$ form a matching and $f$ consists of one vertex from each of $e\_1, e\_2, e\_3$. In this case $\mathrm{mw}(H)=1$.


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**](http://dx.doi.org/10.1007/s004930170001), Combinatorica 21, No. 1, 1-4 (2001). [ZBL1107.05307](https://zbmath.org/?q=an:1107.05307). where he uses the fact that $\tau(H)\leq 2\mathrm{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.



Relationship between minimum vertex cover and matching width
Your suspicion is correct. The following hypergraph $H$ provides a negative answer to your question. Let $V=\{0,1,\dots, 11\}$. Then $V=V\_0\cup V\_1\cup V\_2$, where $V\_0=\{0,1,2,3\}$, $V\_1=\{4,5,6,7\}$, and $V\_2=\{8,9,10,11\}$. Let $E(H)$ is a family of all three-element subsets $e$ of $V$, such that $|e\cap V\_i|=1$ for each $i$ and the sum of elements of $e$ equals $0$ modulo $4$. By the construction, $H$ is a 3-partite 3-uniform hypergraph.


We claim that the matching width of $H$ equals $1$. Indeed, let $M$ be any non-empty matching in $H$. Suppose to the contary that $|M|=4$. Then $M$ covers each vertex of $H$ exactly once. Therefore the sum $S$ of vertices covered by $M$ equals $11\cdot 12/2=6$ modulo $4$. On the other hand, a sum of vertices covered by each edge of $M$ equals $0$ modulo $4$, and so does $S$, a contradiction. Therefore, $|M|\le 3$ and the following cases are possible.


1)) $|M|=1$. Then the unique edge of $M$ intersects itself, so $\rho(M)=1$.


2)) $|M|=2$. Let $M=\{\{a\_0,a\_1,a\_2\}, \{b\_0,b\_1,b\_2\}\}$, where $a\_i, b\_i\in V\_i$ for each $i$. There exists a unique number $c\in V\_2$ such that $a\_0+b\_1+c\_2=0\pmod 4$. Then $\{a\_0, b\_1,c\_2\}$ is an edge of $H$ intersecting each edge of $M$, so $\rho(M)=1$.


3)) $|M|=3$. Let $M=\{\{a\_0,a\_1,a\_2\}, \{b\_0,b\_1,b\_2\}, \{c\_0,c\_1,c\_2\}\}$, where $a\_i, b\_i, c\_i\in V\_i$ for each $i$. There exist unique numbers $d\_b, d\_c\in V\_2$ such that $a\_0+b\_1+d\_b=0\pmod 4$ and $a\_0+c\_1+d\_c=0\pmod 4$. Since $b\_1\ne c\_1\pmod 4$, $d\_b\ne d\_c$. Therefore the following cases are possible.


3.1)) $d\_b\in \{a\_2, b\_2, c\_2\}$. If $d\_b=a\_2$ then $b\_1=a\_1$, so $M$ is not a matching, a contradiction. If $d\_b=b\_2$ then $b\_0=a\_0$, so $M$ is not a matching, a contradiction. Thus $d\_b=c\_2$, and so $\{a\_0, b\_1, c\_2\}$ is an edge of $H$ intersecting each edge of $M$, so $\rho(M)=1$.


3.2)) $d\_c\in \{a\_2, b\_2, c\_2\}$. If $d\_c=a\_2$ then $c\_1=a\_1$, so $M$ is not a matching, a contradiction. If $d\_c=c\_2$ then $c\_0=a\_0$, so $M$ is not a matching, a contradiction. Thus $d\_b=b\_2$, and so $\{a\_0, c\_1, b\_2\}$ is an edge of $H$ intersecting each edge of $M$, so $\rho(M)=1$.


Thus $H$ has the matching width $1$.


On the other hand, we claim that $\tau(H)>3$. Indeed, let $Q$ be any three-element subset of $V$. The following cases are possible.


1)) There exists $V\_i$ disjoint from $Q$. Let $V\_j$ and $V\_k$ be the remaining three-partite parts of $V$. Pick arbitrary numbers $v\_i\in V\_j\setminus Q$ and $v\_k\in V\_k\setminus Q $. There exists number $v\_i\in V\_i$ such that $v\_i+v\_j+v\_k=0\pmod 4$. Then $\{v\_i, v\_j, v\_k\}$ is an edge of $H$ disjoint from $Q$.


2)) $|Q\cap V\_i|=1$ for each $i$. Pick any distinct numbers $v\_0\in V\_0\setminus Q$ and $v\_1, u\_1\in V\_1\setminus Q$. There exist unique numbers $v\_2, u\_2\in V\_2$ such that $v\_0+v\_1+v\_2=0\pmod 4$ and $v\_0+u\_1+u\_2=0\pmod 4$. Since $v\_1\ne u\_1\pmod 4$, $v\_2\ne u\_2$. Therefore the following cases are possible.


2.1)) $v\_2\not\in Q$. Then $\{v\_0, v\_1, v\_2\}$ is an edge of $H$ disjoint from $Q$.


2.2)) $u\_2\not\in Q$. Then $\{v\_0, u\_1, u\_2\}$ is an edge of $H$ disjoint from $Q$.


