7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ As far as I understand, they do not assume regularity, but they do assume that all $r$ sides of the graph contain the same number of vertices ($n$). $\endgroup$ Jul 15 '20 at 13:48
1
$\begingroup$

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.

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