While doing research I came unto the following problem:

Given a hypergraph $H$ $r-partite$, $r-uniform$ (a r-graph, each edge contains r vertices), >$k- regular$ (all vertices have regular degree) and $n-balanced$ (each partition contain n vertices).

Does H contain a perfect matching (an independent set of edges that covers all vertices)?

In literature I've found results by Aharoni, Haxell, Alon, Rödl and others, with sufficient conditions, but none seem to contain these hypothesis over the graph. Any suggestions or pointers to literature would be greatly appreciated.


Instead of asking wether H contains a perfect matching, what would be sufficient conditions for H to have a perfect matching? More specifically, what invariants are important in this kind of problem?

So far I've seen $\delta(H)$ and $|H|$ or $|V|$. I wonder if there are sufficient conditions which do not contain hypothesis over the size of partitions or of the graph.


The answer is no. That is, already for $n=3$, $r = 3$ and $k = 2$ there is an $r$-partite $r$-uniform $k$-regular hypergraph that doesn't contain a perfect matching.

Let $v_1,v_2,v_3$ be the first part, $u_1,u_2,u_3$ be the second part and $w_1,w_2,w_3$ the third. Let the hyperedges be $$(v_1,u_1,w_1),(v_1,u_2,w_2),(v_2,u_2,w_1),(v_2,u_3,w_3),(v_3,u_3,w_3),(v_3,u_1,w_2) .$$

It is easy to verify that the resulting hypergraph is 2-regular. However, there is no perfect matching. To see this, consider $w_1$. It belongs to the first and third edge. If we take the first, then we can't take the second (because both contain $v_1$) and so we must take the third edge if we want to cover $u_2$. However, this is impossible because then $w_1$ is covered twice. Hence there is no perfect matching.


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.