Portal de Periódicos da CAPES

Perfect matchings in large uniform hypergraphs with large minimum collective degree

2008; Elsevier BV; Volume: 116; Issue: 3 Linguagem: Inglês

10.1016/j.jcta.2008.10.002

1096-0899

Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi,

Graph theory and applications

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.