On several partitioning problems of Bollobás and Scott

Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. Let G be a hypergraph with mi edges of size i for i=1,2. We show that for any integer k⩾1, V(G) admits a partition into k sets each containing at most m1/k+m2/k2+o(m2) edges, establishing a conjecture of Bollobás and Scott. We also prove that V(G) admits a partition into k⩾3 sets, each meeting at least m1/k+m2/(k−1)+o(m2) edges, which, for large graphs, implies a conjecture of Bollobás and Scott (the conjecture is for all graphs). For k=2, we prove that V(G) admits a partition into two sets each meeting at least m1/2+3m2/4+o(m2) edges, which solves a special case of a more general problem of Bollobás and Scott.