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

Rödl, Vojtěch, et al. "A note on perfect matchings in uniform hypergraphs with large minimum collective degree." Commentationes Mathematicae Universitatis Carolinae 49.4 (2008): 633-636. <http://eudml.org/doc/250488>.

@article{Rödl2008,
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ödl, Ruci’nski, and Szemerédi 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 \lbrace 3/2, 2, 5/2, 3\rbrace $ 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.},
author = {Rödl, Vojtěch, Ruciński, Andrzej, Schacht, Mathias, Szemerédi, Endre},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {hypergraph; perfect matching; hypergraph; perfect matching},
language = {eng},
number = {4},
pages = {633-636},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {A note on perfect matchings in uniform hypergraphs with large minimum collective degree},
url = {http://eudml.org/doc/250488},
volume = {49},
year = {2008},
}

TY - JOUR
AU - Rödl, Vojtěch
AU - Ruciński, Andrzej
AU - Schacht, Mathias
AU - Szemerédi, Endre
TI - A note on perfect matchings in uniform hypergraphs with large minimum collective degree
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2008
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 49
IS - 4
SP - 633
EP - 636
AB - 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ödl, Ruci’nski, and Szemerédi 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 \lbrace 3/2, 2, 5/2, 3\rbrace $ 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.
LA - eng
KW - hypergraph; perfect matching; hypergraph; perfect matching
UR - http://eudml.org/doc/250488
ER -