Judicious partitions of 3-uniform hypergraphs (Q1972352): Difference between revisions

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.