Perfect matching in a vertex-transitive hypergraph

2012-03-29T18:31:41Z

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.

Answer by domotorp for Perfect matching in a vertex-transitive hypergraph

2012-03-31T14:10:51Z

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

Perfect matching in a vertex-transitive hypergraph - MathOverflow

Perfect matching in a vertex-transitive hypergraph

Answer by domotorp for Perfect matching in a vertex-transitive hypergraph