Judicious Partitioning of Hypergraphs with Edges of Size at Most 2†. (16th August 2016) - HOU, JIANFENG; ZENG, QINGHOU
Abstract : 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_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).