Near perfect matchings in k-uniform hypergraphs II

Jie Han*

*此作品的通讯作者

科研成果: 期刊稿件文章同行评审

9 引用 (Scopus)

摘要

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' 的科研主题。它们共同构成独一无二的指纹。

引用此