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!


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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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