Judicious partitions of uniform hypergraphs (Q484549): Difference between revisions

It is known that the vertices of any graph with \(m\) edges may be partitioned into two parts so that each part meets at least \(\frac{2}{3} m\) edges. \textit{B. Bollobás} et al. [Contemp. Math. 147, 161--165 (1993; Zbl 0787.05053)] conjectured that the vertices of any \(r\)-uniform hypergraph with \(m\) edges may be partitioned into \(r\) classes such that each part meets at least \(\frac{r}{2r-1} m\) edges. The author recently proved the conjecture for the case \(r=3\), see [the author, Combinatorica 32, No. 4, 451--471 (2012; Zbl 1299.05184)]. In this paper, a weaker result is established: for each \(r \geq 4\), a partition into \(r\) classes may be found in which each class meets at least \(\frac{r}{3r-4} m\) edges. This is a significant improvement on previous bounds. All results obtained in this paper apply to hypergraphs with repeated edges.