Judicious Bisection of Hypergraphs  

作　　者：Yu Cong TANG Xin XU Guang Hui WANG 

机构地区：[1]Academy of Mathematics and Systems Science, Chinese Academy of Sciences [2]School of Mathematics, Shandong University

出　　处：《Acta Mathematica Sinica,English Series》2016年第5期579-584,共6页数学学报（英文版）

摘　　要：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 ni edges of size i for i = 1, 2,…, k, then G admits a bisection in which each vertex class spans at mostm1/2＋1/4m2＋…＋（1/2^k）mk＋o（m1＋…＋mk）edges, where G is dense enough or △（G） =o（n） but has no isolated vertex, which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.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 ni edges of size i for i = 1, 2,…, k, then G admits a bisection in which each vertex class spans at mostm1/2＋1/4m2＋…＋（1/2^k）mk＋o（m1＋…＋mk）edges, where G is dense enough or △（G） =o（n） but has no isolated vertex, which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.

关 键 词：PARTITION judicious bisection HYPERGRAPH 

分 类 号：O157.5[理学—数学]