Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs
By Jie Han. 2014
54 citations recorded by the source corpus.
For any $\gamma>0$, Keevash, Knox and Mycroft constructed a polynomial-time algorithm to determine 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 structure 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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/42f66813e2aca6a90f0b9e600de1010d20b9606a
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- Recent advances on Dirac-type problems for hypergraphs (2015, background): “Hàn, Person and Schacht [26] proved that m1(3, n) = (5/9 + o(1))n ≈ δ1(H0(n, 3)).”