# 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|: 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.

• Is not $\rho(M)$ always equal to $|M|$? Oct 5, 2020 at 8:46

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

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