12
$\begingroup$

I would like to know if there exists a version of König's theorem for tripartite $3$-graphs.

In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ equal to the union of three disjoint subsets $A,B,C$) and $T$ is a set of hyperedges $\{v_1,v_2,v_3\}$, with $v_1 \in A, v_2 \in B, v_3 \in C$. A matching is a collection of hyperedges such that no two of them share a vertex. A cover is a set of vertices that meets every hyperedge.

Is there a relationship between the size of a maximum matching and the size of a minimum cover in $G$.

Any suggestions or references? Thanks in advance!

$\endgroup$
1
  • $\begingroup$ You may also be interested in this result: en.wikipedia.org/wiki/… which says that every balanced hypergraph has the Konig property (so its maximum matching size equals its minimum cover size). I am not sure if every tripartite hypergraph is balanced. $\endgroup$ – Erel Segal-Halevi Jul 7 '20 at 17:31
17
$\begingroup$

This is a special case of Ryser's Conjecture, which states that in an $r$-partite, $r$-uniform hypergraph (with $r>1$)

$\tau \leq (r-1) \nu$,

where $\tau$ is the size of a minimum cover and $\nu$ is the size of a maximum matching. Note that the case $r=2$ is simply König's theorem.

You are interested in the case $r=3$, which was settled by Aharoni. The reference is

Ryser's conjecture for tripartite 3-graphs. Combinatorica 21 (2001), no. 1, 1--4,

and you can find a copy of the paper here.

$\endgroup$
0

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.