| Title:
|
A note on perfect matchings in uniform hypergraphs with large minimum collective degree (English) |
| Author:
|
Rödl, Vojtěch |
| Author:
|
Ruciński, Andrzej |
| Author:
|
Schacht, Mathias |
| Author:
|
Szemerédi, Endre |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
49 |
| Issue:
|
4 |
| Year:
|
2008 |
| Pages:
|
633-636 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
hypergraph |
| Keyword:
|
perfect matching |
| MSC:
|
05C65 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1212.05215 |
| idMR:
|
MR2493942 |
| . |
| Date available:
|
2009-05-05T17:13:31Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119750 |
| . |
| Reference:
|
[1] Aharoni R., Georgakopoulos A., Sprüssel Ph.: Perfect matchings in $r$-partite $r$-graphs.submitted. |
| Reference:
|
[2] Kühn D., Osthus D.: Matchings in hypergraphs of large minimum degree.J. Graph Theory 51 (2006), 4 269-280. Zbl 1087.05041, MR 2207573, 10.1002/jgt.20139 |
| Reference:
|
[3] Rödl V., Ruciński A., Szemerédi E.: An approximative Dirac-type theorem for $k$-uniform hypergraphs.Combinatorica, to appear. MR 2399020 |
| Reference:
|
[4] Rödl V., Ruciński A., Szemerédi E.: Perfect matchings in large uniform hypergraphs with large minimum collective degree.submitted. |
| Reference:
|
[5] Rödl V., Ruciński A., Szemerédi E.: Perfect matchings in uniform hypergraphs with large minimum degree.European J. Combin. 27 (2006), 8 1333-1349. Zbl 1104.05051, MR 2260124, 10.1016/j.ejc.2006.05.008 |
| . |
