# Perfect matching in hypergraphs: tripartite, regular and unbalanced

In a balanced bipartite graph - where both sides have the same size - a sufficient condition for the existence of a perfect matching is that the graph is regular - all vertices have the same degree.

Moreover, if the graph is unbalanced - one side is shorter than the other - it is still sufficient that the graph is 'regular' in the sense that, in each side, all vertices have the same degree. In this case, there exists a matching that is 'perfect' in that it covers all vertices in the shorter side. For example, if $$G = (X\cup Y,E)$$ and $$|X|<|Y|$$ and the degree of each vertex in $$X$$ is $$|E|/|X|$$ and the degree of each vertex in $$Y$$is $$|E|/|Y|$$, then the graph has a matching of size $$|X|$$.

For balanced tripartite hypergraphs, the above theorem does not hold. Zur Luria shows an example with 3 vertices in each side. Here is an even smaller example, with 2 vertices in each side. The sides are {1,2}, {a,b}, {A,B} and the edges {1,a,A}, {1,b,B}, {2,b,A}, {2,a,B}; this graph is 2-regular but does not have a perfect matching.

However, a perfect matching does exist if we make the hypergraph slightly unbalanced: in particular, if $$H = (X\cup Y\cup Z,E)$$ and $$|X|=|Y|=2$$ and $$|Z|=3$$, the degree of each vertex in $$X \cup Y$$ is $$|E|/2$$ and the degree of each vertex in $$Z$$ is $$|E|/3$$, then the hypergraph has a matching of size 2. I proved this by checking all cases (there are not many of them).

Does this idea work for larger hypergraphs? Is there a function $$f(n)$$ such that, if $$|X|=|Y|=n$$ and $$|Z| = f(n)$$, and all vertices in each side have the same degree, then the hypergraph has a matching of size $$n$$?

MY RESULTS SO FAR:

(*) There are many results regarding Perfect matching in high-degree hypergraphs. Some of these results are for $$r$$-partite hypergraphs, but only for balanced ones - they assume that all $$r$$ parts have the same size.

(*) There are many results regarding rainbow matchings. A rainbow matching in a bipartite graph is equivalent to a matching in a tripartite hypergraph. A theorem of Aharoni and Berger (2009) implies that, if $$|Z|=2n-1$$ and the set of neighbors of each $$z\in Z$$ is a matching of size $$n$$, then the hypergraph has a perfect matching. In our case the sets of neighbors need not be matchings - the only constraint is on the degree of each vertex.

(*) If such an $$f$$ exists, then $$f(n)\geq 2n-1$$. Consider a tripartite graph with $$X = \{x_1,\ldots,x_n\}$$ and $$Y = \{y_1,\ldots,y_n\}$$ and $$Z = \{z_1,\ldots,z_{2n-2}\}$$ and the following edges:

• $$(x_1, y_1, z_i), (x_2, y_2, z_i),\ldots, (x_n, y_n, z_i)$$ for $$1 \leq i \leq n-1$$;
• $$(x_1, y_2, z_i), (x_2, y_3, z_i),\ldots, (x_n, y_1, z_i)$$ for $$n\leq i\leq 2n-2$$.

All in all, there are $$n(2n-2)$$ edges, the degree of each vertex in $$X\cup Y$$ is $$2n-2$$ and the degree of each vertex in $$Z$$ is $$n$$, so the hypergraph is regular. But the largest matching it contains is of size $$n-1$$. For example, the matching $$(x_i,y_i,z_i)$$ for $$1 \leq i \leq n-1$$ is a matching, but a larger matching does not exist.

Is $$f(n) = 2n-1$$ sufficient?

• When you write if ... all vertices in each side have the same degree, then the graph has a matching, do you really mean graph or, maybe, hypergraph?
– Seva
Jul 15, 2020 at 16:54
• @Seva yes, I meant hypergraph. fixed Jul 15, 2020 at 17:20