Perfect matchings of a regular, uniform, partite hypergraph

Question

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically interested in the $r=3$ case, but any general information is good. So far I have not been able to find a reference that discusses this particular case.

In the question link to above, he is not requiring that the $k$ (for $k$-regular) be the same as the $r$ (for $r$-uniform and $r$-partite), and the example given in the solution uses a case where $k\neq r$.

Any indication on where I might find references for this case or even just the theorems themselves (with the references) would be greatly appreciated.

Answer 1

Without the regularity assumption, Aharoni, Georgakopoulos and Sprüssel have a paper on this topic:

"Perfect matchings in r-partite r-graphs"

https://www.sciencedirect.com/science/article/pii/S0195669808000644

They give a pretty stringent, yet tight sufficient condition. In the discussion section, they speculate many other possible sufficient conditions, which might have been proved or disproved by this point. Perhaps digging through the many Google scholar citations might be helpful.

Answer 2

Here is a 3-regular 3-partite 3-uniform hypergraph with 3 vertices in each part having no perfect matching. This example generalizes in a straightforward way to give a $d$-regular $k$-partite $k$-uniform hypergraph with $d$ vertices in each part having no perfect matching for all $d$ and $k$.

$x_1y_1z_1$
$x_1y_2z_2$
$x_1y_3z_3$
$x_2y_1z_1$
$x_2y_2z_2$
$x_2y_3z_3$
$x_3y_1z_2$
$x_3y_2z_3$
$x_3y_3z_1$

As for sufficient conditions, I think this is a very natural question as it attempts to generalize the specific fact that any regular bipartite graph has a perfect matching (and thus can be decomposed into perfect matchings). I would look at "Hall's Theorem for Hypergraphs" by Aharoni and Haxell as a starting point, but I can't recall any results which specifically focus on the regular case.

Answer 3

For $r = 3$, if we drop the $3$-partite condition, this is RX3C. If we drop $3$-regular, this is 3DM.

3DM is NP-complete, even when the degree is bounded by $3$ (Garey and johnson).

We can get $3$-regular using the same trick than for proving that RX3C is NP-complete, but reducing from 3DM with degree bounded by $3$ (see Gonzalez, Teofilo F., Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci. 38, 293-306 (1985). ZBL0567.62048)

While we don't have a 3-regular hypergraph, we find three vertices $x, y, z$ with $(x, y, z) \in X\times Y\times Z$ that these are each contained in less than $3$ triplets (we can always find such vertices because the sum of degrees in $X, Y$ and $Z$ are always equal), we add the triplets $(x, e_2, e_3), (e_1, y, e_3), (e_1, e_2, z), (e_1, e_2, e_3)$.

It is thus unlikely that there exist useful necessary and sufficient conditions.