Abstract
Suppose k lØ n and H is an n-vertex k-uniform hypergraph. A near perfect matching in H is a matching of size [n/k]. 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 for various cases. Our proof makes use of the lattice-based absorbing method that we used recently to solve two other problems on matching and tilings for hypergraphs.
| Original language | English |
|---|---|
| Pages (from-to) | 1453-1469 |
| Number of pages | 17 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 30 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2016 |
| Externally published | Yes |
Keywords
- Absorbing method
- Hypergraph
- Perfect matching
Fingerprint
Dive into the research topics of 'Near perfect matchings in k-uniform hypergraphs II'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver