Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Matchings in k-partite k-uniform hypergraphs

Texto completo
Autor(es):
Han, Jie [1] ; Zang, Chuanyun [2] ; Zhao, Yi [2]
Número total de Autores: 3
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
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; 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: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/18641-5 - Circuitos Hamiltonianos e problemas de ladrilhamento em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado