7
$\begingroup$

While doing research I came unto the following problem:

Given a hypergraph $H$ which is $r$-partite, $r$-uniform (each edge contains exactly $r$ vertices), $k$-regular (each vertex is contained in exactly $k$ edges) and $n$-balanced (each partition contains $n$ vertices).

Does H contain a perfect matching (an independent set of edges that covers all vertices)?

In literature I've found results by Aharoni, Haxell, Alon, Rödl and others, with sufficient conditions, but none seem to contain these hypothesis over the graph. Any suggestions or pointers to literature would be greatly appreciated.

EDIT:

Instead of asking wether H contains a perfect matching, what would be sufficient conditions for H to have a perfect matching? More specifically, what invariants are important in this kind of problem?

So far I've seen $\delta(H)$ and $|H|$ or $|V|$. I wonder if there are sufficient conditions which do not contain hypothesis over the size of partitions or of the graph.

$\endgroup$
7
$\begingroup$

The answer is no. That is, already for $n=3$, $r = 3$ and $k = 2$ there is an $r$-partite $r$-uniform $k$-regular hypergraph that doesn't contain a perfect matching.

Let $v_1,v_2,v_3$ be the first part, $u_1,u_2,u_3$ be the second part and $w_1,w_2,w_3$ the third. Let the hyperedges be $$(v_1,u_1,w_1),(v_1,u_2,w_2),(v_2,u_2,w_1),(v_2,u_3,w_3),(v_3,u_3,w_3),(v_3,u_1,w_2) .$$

It is easy to verify that the resulting hypergraph is 2-regular. However, there is no perfect matching. To see this, consider $w_1$. It belongs to the first and third edge. If we take the first, then we can't take the second (because both contain $v_1$) and so we must take the third edge if we want to cover $u_2$. However, this is impossible because then $w_1$ is covered twice. Hence there is no perfect matching.

$\endgroup$
1
  • $\begingroup$ I gave this answer mathoverflow.net/a/368902/17798 in a related question, but maybe it makes more sense to put it here as it generalizes the above example given by @Zur Luria $\endgroup$ – Louis D Sep 11 '20 at 15:11
1
$\begingroup$

There are many tempting conjectures to be made about perfect matchings in hypergraphs, most of which seem to be disprovable via the probabilistic method. If that doesn't quite work out, as the below paper of Adam Wagner points out, we have a perhaps humbler tool in hand, namely, linear programming.

https://www.sciencedirect.com/science/article/pii/S0097316519301116

For example, the author gives a small computer generated counterexample to a conjecture of Aharoni and Howard about rainbow matchings in graphs (which can be expressed as a matching problem for 3-uniform 3-partite hypergraphs).

If you have a conjectural sufficient condition in mind, it might be a good idea to see if the problem can be expressed as a linear program, and then have a computer do a sanity check for you on small examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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