Near Perfect Matchings in k-uniform Hypergraphs II
classification
🧮 math.CO
keywords
perfectmatchingmatchingsnearconjecturebarrierdivisibilitygeneralizes
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.