Vojt\v ech R\"odl, Andrzej Ruci\'nski, Mathias Schacht, Endre Szemer\'edi
A note on perfect matchings in uniform hypergraphs with large minimum collective degree

Comment.Math.Univ.Carolin. 49,4 (2008) 633-636.

Abstract:For an integer $k\ge 2$ and a $k$-uniform hypergraph $H$, let $\delta _{k-1}(H)$ be the largest integer $d$ such that every $(k-1)$-element set of vertices of $H$ belongs to at least $d$ edges of $H$. Further, let $t(k,n)$ be the smallest integer $t$ such that every $k$-uniform hypergraph on $n$ vertices and with $\delta _{k-1}(H)\ge t$ contains a perfect matching. The parameter $t(k,n)$ has been completely determined for all $k$ and large $n$ divisible by $k$ by R\"odl, Ruci\'nski, and Szemer\'edi in [{Perfect matchings in large uniform hypergraphs with large minimum collective degree}, submitted]. The values of $t(k,n)$ are very close to $n/2-k$. In fact, the function $t(k,n)=n/2-k+c_{n,k}$, where $c_{n,k}\in \{3/2, 2, 5/2, 3\}$ depends on the parity of $k$ and $n$. The aim of this short note is to present a simple proof of an only slightly weaker bound: $t(k,n)\le n/2+k/4$. Our argument is based on an idea used in a recent paper of Aharoni, Georgakopoulos, and Spr\"ussel.

Keywords: hypergraph, perfect matching
AMS Subject Classification: Primary 05C70; Secondary 05C65