Perfect Matchings in 4-uniform hypergraphsImdadullah KhanDepartment of Computer Science
Rutgers UniversityNew Brunswick, NJ, USA 08903
[email protected] 10, 2011AbstractA perfect matching in a 4-uniform hypergraph is a subset of bn
4
c disjoint edges. We provethat if H is a sufficiently large 4-uniform hypergraph on n = 4k vertices such that every vertexbelongs to more than
(
n−1
3)
−
(
3n/4
3)
edges then H contains a perfect matching. This bound istight and settles a conjecture of Ha
