A note on perfect matchings in uniform hypergraphs with large minimum collective degree

Rödl, Vojtěch ; Ruciński, Andrzej ; Schacht, Mathias ; Szemerédi, Endre

Commentationes Mathematicae Universitatis Carolinae, Tome 49 (2008) no. 4, pp. 633-636.

Résumé

For an integer $k\ge2$ 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ödl, Ruci'nski, and Szemerédi in [{\it 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.

Détail

Classification : 05C65, 05C70
Keywords: hypergraph; perfect matching