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?
