A folklore result on matchings in graphs states that if G is a bipartite graph whose vertex classes A and B each have size n, with deg(u)≥a for every u∈A and deg(v)≥b for every v∈B, then G admits a matching of size min{n,a+b}. In this paper we establish the analogous result for large k-partite k-uniform hypergraphs, answering a question of Han, Zang and Zhao, who previously demonstrated that this result holds under the additional condition that the minimum degrees into at least two of the vertex classes are large. A key part of our proof is a study of rainbow matchings under a combination of degree and multiplicity conditions, which may be of independent interest.
Mathematics Subject Classifications: 05C65, 05C70
Keywords: Matchings, Hypergraphs
Cookie SettingseScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.