摘要
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.
源语言 | 英语 |
---|---|
页(从-至) | 1453-1469 |
页数 | 17 |
期刊 | SIAM Journal on Discrete Mathematics |
卷 | 30 |
期 | 3 |
DOI | |
出版状态 | 已出版 - 2016 |
已对外发布 | 是 |
指纹
探究 'Near perfect matchings in k-uniform hypergraphs II' 的科研主题。它们共同构成独一无二的指纹。引用此
Han, J. (2016). Near perfect matchings in k-uniform hypergraphs II. SIAM Journal on Discrete Mathematics, 30(3), 1453-1469. https://doi.org/10.1137/15M1029990