Judicious partitions of 3-uniform hypergraphs
type: Item
instance of: scholarly article
title: Judicious partitions of 3-uniform hypergraphs
zbMATH Open document ID: 0943.05058
author: Béla Bollobás
author: Alex Scott
published in: European Journal of Combinatorics
publication date: 2000-04-26T00:00:00Z
review text: A conjecture of Bolloás and Thomason asserts that, for \(r\geq 1\), the vertex set of every \(r\)-uniform hypergraph can be partitioned into \(r\) classes so that every class meets at least \(rm/(2r- 1)\) edges. This paper offers some partial results in support of this conjecture. It is proved that the vertices of a 3-uniform hypergraph with \(m\) edges can be partitioned into 3 classes such that every class meets at least \((5m- 1)/9\) edges. It is also proved that for \(r>3\) the vertex set of an \(r\)-uniform hypergraph can be partitioned into \(r\) classes such that each class meets at least \(0.27m\) edges. The paper concludes with two related conjectures. A factor of \(m\) was inadvertently omitted from the last conjectured bound on page 299.
reviewed by: Saul Stahl
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1436078
zbMATH Keywords: partitions
zbMATH Keywords: hypergraph
MaRDI profile type: Publication
full work available at URL: eujc.1998.0266
OpenAlex ID: W2050977427
cites work: Bipartite subgraphs
cites work: Q3320411
cites work: Q4273842
cites work: Judicious partitions of hypergraphs
cites work: Some Extremal Properties of Bipartite Subgraphs
cites work: How to make a graph bipartite
cites work: The size of the largest bipartite subgraphs
cites work: Some simplified NP-complete graph problems
cites work: Über die Approximation von Zahlen durch Reihen mit positiven Gliedern
DOI: 10.1006/EUJC.1998.0266
description: scientific article; zbMATH DE number 1436078