Matchings in k-partite k-uniform hypergraphs

Author(s)

Han, Jie ^[1] ; Zang, Chuanyun ^[2] ; Zhao, Yi ^[2]

Affiliation

^[1] Univ Rhode Isl, Dept Math, 5 Lippitt Rd, Kingston, RI 02881 - USA

^[2] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 - USA

• Document type: Journal article
• Source: JOURNAL OF GRAPH THEORY; v. 95, n. 1 NOV 2019.
• Web of Science Citations: 0

Abstract

For k >= 3 and epsilon>0, let H be a k-partite k-graph with parts V1, horizontal ellipsis ,Vk each of size n, where n is sufficiently large. Assume that for each i is an element of{[}k], every (k-1)-set in j is an element of{[}k]\textbackslash{}[i]Vj lies in at least ai edges, and a1 >= a2 >= MIDLINE HORIZONTAL ELLIPSIS >= ak. We show that if a1,a2 >=epsilon n, then H contains a matching of size min[n-1, n-ary sumation i is an element of{[}k]ai]. In particular, H contains a matching of size n-1 if each crossing (k-1)-set lies in at least left ceiling n/k right ceiling edges, or each crossing (k-1)-set lies in at least Ln/k<SIC> RIGHT FLOOR edges and n equivalent to 1modk. This special case answers a question of Rodl and Rucinski and was independently obtained by Lu, Wang, and Yu. The proof of Lu, Wang, and Yu closely follows the approach of Han by using the absorbing method and considering an extremal case. In contrast, our result is more general and its proof is thus more involved: it uses a more complex absorbing method and deals with two extremal cases. (AU)

• FAPESP's process: 15/07869-8 - Perfect matchings and Tilings in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral