Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In connection with this MO problem, I wonder whether the hypergraph in question was actually vertex-transitive. And so, as a natural variation (and, perhaps, a refinement):

If the vertex set of a vertex-transitive hypergraph $H$ can be partitioned as $V_1\cup\cdots\cup V_r$, so that every edge of $H$ contains exactly one vertex from each of the partite sets $V_i$, what reasonable conditions guarantee that $H$ possesses a perfect matching?

(As an example of a reasonable condition: $H$ is non-empty. An unreasonable condition would be that $H$ is (almost) complete in the sense that it contains the edge $\{v_1,\ldots, v_r\}$ for (almost) any $v_1\in V_1,\ldots, v_r\in V_r$.)

The case $r=2$ is easy: we are then looking at vertex-transitive bipartite graphs, and every such graph has a perfect matching by Hall's marriage theorem (provided it is non-empty). Indeed, it suffices that the graph be regular. For $r=3$ vertex-transitivity is insufficient as shows, for instance, the following construction. Let $G$ be a finite abelian group of order divisible by $2$, but not by $4$. Let $V_1,V_2,V_3$ be (disjoint) copies of $G$, and consider the hypergraph $H$ on the vertex set $V_1\cup V_2\cup V_3$ whose edges are all triples $(v_1,v_2,v_3)$ with $v_1+v_2+v_3=0$. If a perfect matching in $H$ existed, then the sum of all elements of $G$, multiplied by $3$, would be equal to $0$, which is not the case.

share|improve this question

1 Answer 1

This answer is not for vertex transitive hypergraphs (I have not noticed that condition)!

No simple necessary and sufficient condition can exists as 3DM is NP-complete:

Of course, if you are only looking for a sufficient condition, one can come up with several, eg. see: http://arxiv.org/abs/1101.5830 where it is proved by Imdadullah Khan that "A perfect matching in a 3-uniform hypergraph on $n=3k$ vertices is a subset of $\frac{n}{3}$ disjoint edges. We prove that if $H$ is a 3-uniform hypergraph on $n=3k$ vertices such that every vertex belongs to at least ${n-1\choose 2} - {2n/3\choose 2}+1$ edges then $H$ contains a perfect matching. We give a construction to show that this result is best possible."

share|improve this answer
Thanks! I was unaware of the three-dimensional matching problem. As to the second part of your answer, the degree assumptions are exactly what I had in mind mentioning "unreasonable conditions"... –  Seva Mar 31 '12 at 18:31
And, by the way: does the problems remain NP-complete if we confine to vertex-transitive hypergraphs? –  Seva Mar 31 '12 at 18:36
One more remark: there is no necessary and sufficient condition which is easy to check computationally. However, there still can possibly exist a "logically simple" and useful condition! –  Seva Mar 31 '12 at 18:49
Oh, I have no noticed you ask for vertex transitive... I don't know anything about that for hypergraphs. For non-empty graphs with an even number of vertices you must have a perfect matching in this case, this follows from the Gallai-Edmonds Decomposition. Do you have a counterexample for hypergraphs? –  domotorp Apr 2 '12 at 7:12
I appended an answer at the end of my original post. –  Seva Apr 2 '12 at 12:40

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.