Relationship between minimum vertex cover and matching width

Question

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, Combinatorica 21, No. 1, 1-4 (2001). ZBL1107.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.

Answer 1

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$.

Answer 2

Thinking about Alex Ravsky's example reminded me of a construction I saw here arxiv.org/abs/1902.05055 (top of page 18) which was used in a related, but different context. I just checked that their construction with r=s=3 also provides a negative answer to my question.

By modifying a different construction from arxiv.org/abs/1902.05055 (page 16), I was able to come up with an example which answers my question negatively and I think is considerably easier to verify. So I will share that here.

Let $H=(X\cup Y\cup Z,E)$ where $X=\{x_0, x_1, x_{00}, x_{01}, x_{10}, x_{11}\}$, $Y=\{y_0, y_1, y_{00}, y_{01}, y_{10}, y_{11}\}$, $Z=\{z_0, z_1, z_{00}, z_{01}, z_{10}, z_{11}\}$ and let $E=\{x_iy_jz_k: i,j,k\in \{0,1\}\}\cup \{x_iy_jz_{ij}: i,j\in \{0,1\}\}\cup \{x_iz_jy_{ij}: i,j\in \{0,1\}\}\cup \{y_iz_jx_{ij}: i,j\in \{0,1\}\}$

Note that every edge contains at least two vertices from $\{x_0, x_1, y_0, y_1, z_0, z_1\}$ and this makes it easy to check that for every matching $M$ (the largest of which has size 3) there is one edge from $\{x_iy_jz_k: i,j,k\in \{0,1\}\}$ which intersects all the edges in $M$; i.e. $\mathrm{mw}(H)=1$. Also it is easy to see $\tau(H)=4$.