The Asymptotic Combinatorics of Permutations and Flag Algebras
Metrics in the context of information theory and error correcting codes
Structural and extremal properties of graphs and hypergraphs
| Full text | |
| Author(s): |
Han, Jie
Total Authors: 1
|
| Document type: | Journal article |
| Source: | TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY; v. 369, n. 7, p. 22-pg., 2017-07-01. |
| 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 Karpinski, Rucinski and Szymanska completely. Our proof uses a lattice-based absorbing method. (AU) | |
| FAPESP's process: | 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 15/07869-8 - Perfect matchings and Tilings in hypergraphs |
| Grantee: | Jie Han |
| Support Opportunities: | Scholarships abroad - Research Internship - Post-doctor |