Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
hypergraph; perfect matching
hypergraph; perfect matching
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.
References:
[1] Aharoni R., Georgakopoulos A., Sprüssel Ph.: Perfect matchings in $r$-partite $r$-graphs. submitted.
[2] Kühn D., Osthus D.: Matchings in hypergraphs of large minimum degree. J. Graph Theory 51 (2006), 4 269-280. DOI 10.1002/jgt.20139 | MR 2207573 | Zbl 1087.05041
[3] Rödl V., Ruciński A., Szemerédi E.: An approximative Dirac-type theorem for $k$-uniform hypergraphs. Combinatorica, to appear. MR 2399020
[4] Rödl V., Ruciński A., Szemerédi E.: Perfect matchings in large uniform hypergraphs with large minimum collective degree. submitted.
[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. DOI 10.1016/j.ejc.2006.05.008 | MR 2260124 | Zbl 1104.05051
Search
Partner of
