Judicious Partitioning of Hypergraphs with Edges of Size at Most 2†. (16th August 2016)

• Record Type: Journal Article
• Authors: HOU, JIANFENG; ZENG, QINGHOU
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 2(2017:Mar.)
• Page Start: 267
• Page End: 284
• Publication Date: 2016-08-16
• Subjects: Primary 05C35, -- Secondary 05C75; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000274
• Languages: English
• ISSNs: 0963-5483

Abstract

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).