Near Perfect Matchings in $k$-uniform Hypergraphs II

Abstract

Suppose $k\nmid n$ and $H$ is an $n$-vertex $k$-uniform hypergraph. A near perfect matching in $H$ is a matching of size $\lfloor n/k\rfloor$. We give a divisibility barrier construction that prevents the existence of near perfect matchings in $H$. This generalizes the divisibility barrier for perfect matchings. We give a conjecture on the minimum $d$-degree threshold forcing a (near) perfect matching in $H$ which generalizes a well-known conjecture on perfect matchings. We also verify our conjecture in various cases. Our proof makes use of the lattice-based absorbing method that the author used recently to solve two other problems on matching and tilings for hypergraphs.

13 pages, 0 figure, Corrected a very minor error in Lemma 3.4

References in corpus (2)

• Polynomial-time perfect matchings in dense hypergraphs
• Near Perfect Matchings in $k$-uniform Hypergraphs