A note on perfect matchings in uniform hypergraphs with large minimum collective degree
Commentationes Mathematicae Universitatis Carolinae, Tome 49 (2008) no. 4, pp. 633-636
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library
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.
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.
@article{CMUC_2008_49_4_a7,
author = {R\"odl, Vojt\v{e}ch and Ruci\'nski, Andrzej and Schacht, Mathias and Szemer\'edi, Endre},
title = {A note on perfect matchings in uniform hypergraphs with large minimum collective degree},
journal = {Commentationes Mathematicae Universitatis Carolinae},
pages = {633--636},
year = {2008},
volume = {49},
number = {4},
mrnumber = {2493942},
zbl = {1212.05215},
language = {en},
url = {http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a7/}
}
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 SP - 633 EP - 636 VL - 49 IS - 4 UR - http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a7/ LA - en ID - CMUC_2008_49_4_a7 ER -
%0 Journal Article %A Rödl, Vojtěch %A Ruciński, Andrzej %A Schacht, Mathias %A Szemerédi, Endre %T A note on perfect matchings in uniform hypergraphs with large minimum collective degree %J Commentationes Mathematicae Universitatis Carolinae %D 2008 %P 633-636 %V 49 %N 4 %U http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a7/ %G en %F CMUC_2008_49_4_a7
Rödl, Vojtěch; Ruciński, Andrzej; Schacht, Mathias; Szemerédi, Endre. A note on perfect matchings in uniform hypergraphs with large minimum collective degree. Commentationes Mathematicae Universitatis Carolinae, Tome 49 (2008) no. 4, pp. 633-636. http://geodesic.mathdoc.fr/item/CMUC_2008_49_4_a7/