We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A Note on Exact Minimum Degree Threshold for Fractional Perfect Matchings.
- Authors
Lu, Hongliang; Yu, Xingxing
- Abstract
Rödl, Ruciński, and Szemerédi determined the minimum (k - 1) -degree threshold for the existence of fractional perfect matchings in k-uniform hypergrahs, and Kühn, Osthus, and Townsend extended this result by asymptotically determining the d-degree threshold for the range k - 1 > d ≥ k / 2 . In this note, we prove the following exact degree threshold: let k, d be positive integers with k ≥ 4 and k - 1 > d ≥ k / 2 , and let n be any integer with n ≥ 2 k (k - 1) + 1 . Then any n-vertex k-uniform hypergraph with minimum d-degree δ d (H) > n - d k - d - n - d - (⌈ n / k ⌉ - 1) k - d contains a fractional perfect matching. This lower bound on the minimum d-degree is best possible. We also determine the minimum d-degree threshold for the existence of fractional matchings of size s, where 0 < s ≤ n / k (when k / 2 ≤ d ≤ k - 1 ), or with s large enough and s ≤ n / k (when 2 k / 5 < d < k / 2 ).
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02475-1