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(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+k-12k^22(km_1+m_2)+O(1). edges. This bound is tight up to O (1).