Perfect matchings in large uniform hypergraphs with large minimum collective degree
Perfect matchings in large uniform hypergraphs with large minimum collective degree
复制标题
DOI：
10.1016/j.jcta.2008.10.002
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
V. Rödl;A. Rucinski;E. Szemerédi
中科院分区：
文献类型：
--
作者：
V. Rödl;A. Rucinski;E. Szemerédi
We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δ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. In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k⩾3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)⩾t contains a perfect matching. For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k. In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.
