MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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