Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 

 

Decision problem for perfect matchings in dense $ k$-uniform hypergraphs


Author: Jie Han
Journal: Trans. Amer. Math. Soc. 369 (2017), 5197-5218
MSC (2010): Primary 05C70, 05C65
DOI: https://doi.org/10.1090/tran/6999
Published electronically: March 17, 2017
MathSciNet review: 3632565
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 Karpiński, Ruciński and Szymańska completely. Our proof uses a lattice-based absorbing method.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C70, 05C65

Retrieve articles in all journals with MSC (2010): 05C70, 05C65


Additional Information

Jie Han
Affiliation: Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil
Email: jhan@ime.usp.br

DOI: https://doi.org/10.1090/tran/6999
Keywords: Perfect matching, hypergraph, absorbing method
Received by editor(s): October 15, 2014
Received by editor(s) in revised form: June 17, 2016
Published electronically: March 17, 2017
Additional Notes: The author was supported by FAPESP (2014/18641-5, 2015/07869-8).
Article copyright: © Copyright 2017 American Mathematical Society