Integer and fractional packings of hypergraphs
type: Item
instance of: scholarly article
title: Integer and fractional packings of hypergraphs
zbMATH Open document ID: 1111.05082
author: Vojtěch Rödl
author: Norihide Tokushige
author: M. Schacht
author: Mark Siggers
published in: Journal of Combinatorial Theory. Series B
publication date: 2007-02-13T00:00:00Z
review text: Let \(F_0\) be a \(k\)-uniform hypergraph. The problem of finding the integer \(F_0\)-packing number \(\nu_{F_0}(\mathcal H)\) of a \(k\)-uniform hypergraph \(\mathcal H\) is NP-hard. Finding the fractional \(F_0\)-packing number \(\nu^*_{F_0}(\mathcal H)\) however can be done in polynomial time. The authors present a lower bound for \(\nu_{F_0}(\mathcal H)\) in terms of \(\nu^*_{F_0}(\mathcal H)\), and they prove that \(\nu_{F_0}(\mathcal H)\geq\nu^*_{F_0}(\mathcal H)- o(| V(\mathcal H)| ^k),\) where \(V(\mathcal H)\) is the vertex set of the \(k\)-uniform hypergraph \(\mathcal H\).
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 5125320
zbMATH Keywords: hypergraph regularity lemma
MaRDI profile type: Publication
full work available at URL: j.jctb.2006.05.006
OpenAlex ID: W1977123275
cites work: The Algorithmic Aspects of the Regularity Lemma
cites work: Q4234075
cites work: Constructive Quasi-Ramsey Numbers and Tournament Ranking
cites work: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
cites work: Near perfect coverings in graphs and hypergraphs
cites work: Extremal problems on set systems
cites work: Quick approximation to matrices and applications
cites work: Lower bounds of tower type for Szemerédi's uniformity lemma
cites work: Nearly-perfect hypergraph packing is in NC
cites work: Integer and fractional packings in dense graphs
cites work: Integer and fractional packings in dense 3‐uniform hypergraphs
cites work: An Algorithmic Version of the Hypergraph Regularity Method
cites work: Hypergraphs, quasi-randomness, and conditions for regularity
cites work: Q4878666
cites work: Asymptotic behavior of the chromatic index for hypergraphs
cites work: Regular Partitions of Hypergraphs: Counting Lemmas
cites work: Regularity Lemma for k-uniform hypergraphs
cites work: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
cites work: Integer and fractional packing of families of graphs
DOI: 10.1016/J.JCTB.2006.05.006
Recommended article: Integer and fractional packing of families of graphs
Recommended article: Integer and fractional packings in dense graphs
Recommended article: Integer and fractional packings in dense 3‐uniform hypergraphs
Recommended article: Q5753985
Recommended article: Q3032297
Recommended article: On the packing numbers in graphs
Recommended article: Packing random graphs and hypergraphs
Recommended article: On the Fractional Covering Number of Hypergraphs
Recommended article: Hypergraph Packing and Sparse Bipartite Ramsey Numbers
Recommended article: A note on packing of uniform hypergraphs
description: scientific article; zbMATH DE number 5125320