Perfect matching in a vertex-transitive hypergraph - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T10:24:50Z http://mathoverflow.net/feeds/question/92596 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92596/perfect-matching-in-a-vertex-transitive-hypergraph Perfect matching in a vertex-transitive hypergraph Seva 2012-03-29T18:31:41Z 2012-04-02T16:12:45Z <p>In connection with <a href="http://mathoverflow.net/questions/92568/perfect-matchings-in-certain-classes-of-hypergraphs" rel="nofollow">this MO problem</a>, I wonder whether the hypergraph in question was actually vertex-transitive. And so, as a natural variation (and, perhaps, a refinement):</p> <blockquote> <p>If the vertex set of a vertex-transitive hypergraph $H$ can be partitioned as <code>$V_1\cup\cdots\cup V_r$</code>, 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?</p> </blockquote> <p>(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 <code>$\{v_1,\ldots, v_r\}$</code> for (almost) any <code>$v_1\in V_1,\ldots, v_r\in V_r$</code>.)</p> <hr> <p>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.</p> http://mathoverflow.net/questions/92596/perfect-matching-in-a-vertex-transitive-hypergraph/92754#92754 Answer by domotorp for Perfect matching in a vertex-transitive hypergraph domotorp 2012-03-31T14:10:51Z 2012-04-02T07:09:11Z <p>This answer is not for vertex transitive hypergraphs (I have not noticed that condition)!</p> <p>No simple necessary and sufficient condition can exists as 3DM is NP-complete:<br> <a href="http://en.wikipedia.org/wiki/3-dimensional_matching" rel="nofollow">http://en.wikipedia.org/wiki/3-dimensional_matching</a></p> <p>Of course, if you are only looking for a sufficient condition, one can come up with several, eg. see: <a href="http://arxiv.org/abs/1101.5830" rel="nofollow">http://arxiv.org/abs/1101.5830</a> 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." </p>