Perfect matchings in large uniform hypergraphs with large minimum collective degree |
| |
Authors: | Vojtech Rödl Andrzej Ruciński Endre Szemerédi |
| |
Institution: | a Emory University, Atlanta, GA, USA b A. Mickiewicz University, Poznań, Poland c Rutgers University, New Brunswick, NJ, USA |
| |
Abstract: | 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. |
| |
Keywords: | Hypergraph Perfect matching Minimum degree |
本文献已被 ScienceDirect 等数据库收录! |
|