3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is not $\rho(M)$ always equal to $|M|$? $\endgroup$ – Fedor Petrov Oct 5 '20 at 8:46
  • 1
    $\begingroup$ @Fedor Petrov. I added an example to address your question. $\endgroup$ – Louis D Oct 5 '20 at 11:31
2
+50
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.