TY - JOUR
T1 - Near Perfect Matchings in k-Uniform Hypergraphs
AU - Han, Jie
N1 - Publisher Copyright:
© Cambridge University Press 2014.
PY - 2015/9/25
Y1 - 2015/9/25
N2 - Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k - 1)-degree of H is at least [n/k], then H contains a matching with [n/k] edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k - 1)-degree n/k + O(logn) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.
AB - Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k - 1)-degree of H is at least [n/k], then H contains a matching with [n/k] edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k - 1)-degree n/k + O(logn) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.
UR - http://www.scopus.com/inward/record.url?scp=84937779420&partnerID=8YFLogxK
U2 - 10.1017/S0963548314000613
DO - 10.1017/S0963548314000613
M3 - Article
AN - SCOPUS:84937779420
SN - 0963-5483
VL - 24
SP - 723
EP - 732
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
IS - 5
ER -