On a hypergraph matching problem

Noga Alon, Raphael Yuster

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

Let H = (V, E) be an r-uniform hypergraph and let ℱ ⊂ 2 V. A matching M of H is (α, ℱ)-perfect if for each ℱ ∈ ℱ, at least α F| vertices of F are covered by M. Our main result is a theorem giving sufficient conditions for an r-uniform hypergraph to have a (1 - ε, ℱ-perfect matching. As a special case of our theorem we obtain the following result. Let K(n, r) denote the complete r-uniform hypergraph with n vertices. Let t and r be fixed positive integers where t ≥ r ≥ 2. Then, K (n, r) can be packed with edge-disjoint copies of K(t, r) such that each vertex is incident with only o(nr-1) unpacked edges. This extends a result of Rödl [9].

Original languageEnglish (US)
Pages (from-to)377-384
Number of pages8
JournalGraphs and Combinatorics
Volume21
Issue number4
DOIs
StatePublished - Dec 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On a hypergraph matching problem'. Together they form a unique fingerprint.

  • Cite this