Integer and fractional packings of hypergraphs

V. Rödl, M. Schacht, M. H. Siggers, N. Tokushige

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number νF0 (H) of a k-uniform hypergraph H is an NP-hard problem. Finding the fractional F0-packing number νF0* (H) however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number νF0 (H) in terms of νF0* (H) and show that νF0 (H) ≥ νF0* (H) - o (| V (H) |k).

Original languageEnglish
Pages (from-to)245-268
Number of pages24
JournalJournal of Combinatorial Theory. Series B
Volume97
Issue number2
DOIs
StatePublished - Mar 2007

Keywords

  • Hypergraph regularity lemma
  • Packings

Fingerprint

Dive into the research topics of 'Integer and fractional packings of hypergraphs'. Together they form a unique fingerprint.

Cite this