Ortogonalidade entre empacotamento de caminhos e partições em conjuntos independen...
Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
Texto completo | |
Autor(es): |
Han, Jie
;
Zang, Chuanyun
;
Zhao, Yi
Número total de Autores: 3
|
Tipo de documento: | Artigo Científico |
Fonte: | JOURNAL OF COMBINATORIAL THEORY SERIES A; v. 149, p. 115-147, JUL 2017. |
Citações Web of Science: | 4 |
Resumo | |
Given positive integers a <= b <= c, let K-a,K-b,K-c be the complete 3-partite 3-uniform hypergraph with three parts of sizes a,b,c. Let H be a 3-uniform hypergraph on n vertices where n is divisible by a+b+c. We asymptotically determine the minimum vertex degree of H that guarantees a perfect K-a,K-b,K-c-tiling, that is, a spanning subgraph of H consisting of vertex-disjoint copies of K-a,K-b,K-c. This partially answers a question of Mycroft, who proved an analogous result with respect to codegree for r-uniform hypergraphs for all r >= 3. Our proof uses a lattice-based absorbing method, the concept of fractional tiling, and a recent result on shadows for 3-graphs. (C) 2017 Elsevier Inc. All rights reserved. (AU) | |
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 |
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: | 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 |