Judicious Partitioning of Hypergraphs with Edges of Size at Most 2

Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. Let k ≥ 2 be an integer and let G be a hypergraph with m i edges of size i for i =1,2. Bollobás and Scott conjectured that G has a partition into k classes, each of which contains at most m₁/k+m₂/k²+O(√m₁+m₂) edges. In this paper, we confirm the conjecture affirmatively by showing that G has a partition into k classes, each of which contains at most m₁/k+m₂/k²+k-12k²√2(km₁+m₂)+O(1). edges. This bound is tight up to O (1).