DECISION PROBLEM FOR PERFECT MATCHINGS IN DENSE k-UNIFORM HYPERGRAPHS

Autor(es)

Han, Jie

• Tipo de documento: Artigo Científico
• Fonte: TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY; v. 369, n. 7, p. 22-pg., 2017-07-01.

Resumo

For any gamma > 0, Keevash, Knox and Mycroft (2015) constructed a polynomial-time algorithm which determines the existence of perfect matchings in any n-vertex k-uniform hypergraph whose minimum codegree is at least n/k + gamma n. We prove a structural theorem that enables us to determine the existence of a perfect matching for any k-uniform hypergraph with minimum codegree at least n/k. This solves a problem of Karpinski, Rucinski and Szymanska completely. Our proof uses a lattice-based absorbing method. (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: 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