Near perfect matchings in k-uniform hypergraphs II

Jie Han*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

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 languageEnglish
Pages (from-to)1453-1469
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number3
DOIs
Publication statusPublished - 2016
Externally publishedYes

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