标题：Judicious Bisection of Hypergraphs
作者：Tang, Yu Cong; Xu, Xin; Wang, Guang Hui
作者机构：[Tang Yu Cong] Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China.;[Xu Xin] Academy of Mathematics and Sys 更多
通讯作者地址：[Tang, YC; Xu, X]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China;[Wang, GH]Shandong Univ, Sch Math, Jinan 250100, Peoples R Ch 更多
关键词：Partition; judicious bisection; hypergraph
摘要：Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously. In this paper, we prove that if G is a hypergraph with n vertices and m(i) edges of size i for i = 1, 2,..., k, then G admits a bisection in which each vertex class spans at most m1/2 + 1/4m(2) + ... + (1/2(k))m(k) + o(m(1) + ... + m(k)) edges, where G is dense enough or Delta(G) = o(n) but has no isolated vertex, which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.