Matchings in k-partite k-uniform hypergraphs

Autor(es)

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

Afiliação do(s) autor(es)

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

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

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF GRAPH THEORY; v. 95, n. 1 NOV 2019.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado