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 mi 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_1/k+m_2/k^2+O(\sqrt{m_1+m_2})$ 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_1/k+m_2/k^2+\ffrac{k-1}{2k^2}\sqrt{2(km_1+m_2)}+O(1)$$. edges. This bound is tight up to O(1).