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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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."

Improve this answer
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented Apr 2, 2012 at 7:12
  • $\begingroup$ I appended an answer at the end of my original post. $\endgroup$
    – Seva
    Commented Apr 2, 2012 at 12:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .