标题: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(tangyucong@amss.ac.cn)
通讯作者地址:[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 更多
来源:数学学报
出版年:2016
卷:32
期:5
页码:579-584
DOI:10.1007/s10114-016-4736-8
关键词: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.
收录类别:CSCD;SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84962799680&doi=10.1007%2fs10114-016-4736-8&partnerID=40&md5=878b6b0860688ed77400515f60903d69
TOP