7
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

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:
http://en.wikipedia.org/wiki/3-dimensional_matching

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."

$\endgroup$
8
  • $\begingroup$ 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"... $\endgroup$
    – Seva
    Mar 31, 2012 at 18:31
  • $\begingroup$ And, by the way: does the problems remain NP-complete if we confine to vertex-transitive hypergraphs? $\endgroup$
    – Seva
    Mar 31, 2012 at 18:36
  • $\begingroup$ 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! $\endgroup$
    – Seva
    Mar 31, 2012 at 18:49
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    Apr 2, 2012 at 7:12
  • $\begingroup$ I appended an answer at the end of my original post. $\endgroup$
    – Seva
    Apr 2, 2012 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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