Judicious partitions of uniform hypergraphs

Abstract

The vertices of any graph with $m$ edges may be partitioned into two parts so that each part meets at least $\frac{2m}{3}$ edges. Bollobás and Thomason conjectured that the vertices of any $r$-uniform hypergraph with $m$ edges may likewise be partitioned into $r$ classes such that each part meets at least $\frac{r}{2r-1}m$ edges. In this paper we prove the weaker statement that, for each $r\ge 4$, a partition into $r$ classes may be found in which each class meets at least $\frac{r}{3r-4}m$ edges, a substantial improvement on previous bounds.

Cited by in corpus (1)

• Balanced Judicious Partition is Fixed-Parameter Tractable