13
$\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!

Improve this question
$\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
    Commented Jul 7, 2020 at 17:31

1 Answer 1

Reset to default
19
$\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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .