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

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

Commentationes Mathematicae Universitatis Carolinae (2008)

- Volume: 49, Issue: 4, page 633-636
- ISSN: 0010-2628

## Access Full Article

top## Abstract

top## How to cite

topRö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 -

## References

top- Aharoni R., Georgakopoulos A., Sprüssel Ph., Perfect matchings in $r$-partite $r$-graphs, submitted.
- Kühn D., Osthus D., 10.1002/jgt.20139, J. Graph Theory 51 (2006), 4 269-280. (2006) Zbl1087.05041MR2207573DOI10.1002/jgt.20139
- Rödl V., Ruciński A., Szemerédi E., An approximative Dirac-type theorem for $k$-uniform hypergraphs, Combinatorica, to appear. MR2399020
- Rödl V., Ruciński A., Szemerédi E., Perfect matchings in large uniform hypergraphs with large minimum collective degree, submitted.
- Rödl V., Ruciński A., Szemerédi E., 10.1016/j.ejc.2006.05.008, European J. Combin. 27 (2006), 8 1333-1349. (2006) Zbl1104.05051MR2260124DOI10.1016/j.ejc.2006.05.008

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.