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 -