KMS Of Academy of mathematics and systems sciences, CAS
Judicious Bisection of Hypergraphs | |
Tang, Yu Cong1; Xu, Xin1; Wang, Guang Hui2 | |
2016-05-01 | |
发表期刊 | ACTA MATHEMATICA SINICA-ENGLISH SERIES |
ISSN | 1439-8516 |
卷号 | 32期号:5页码:579-584 |
摘要 | 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. |
关键词 | Partition judicious bisection hypergraph |
DOI | 10.1007/s10114-016-4736-8 |
语种 | 英语 |
WOS研究方向 | Mathematics |
WOS类目 | Mathematics, Applied ; Mathematics |
WOS记录号 | WOS:000373583200006 |
出版者 | SPRINGER HEIDELBERG |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/22460 |
专题 | 中国科学院数学与系统科学研究院 |
通讯作者 | Tang, Yu Cong; Xu, Xin; Wang, Guang Hui |
作者单位 | 1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Shandong Univ, Sch Math, Jinan 250100, Peoples R China |
推荐引用方式 GB/T 7714 | Tang, Yu Cong,Xu, Xin,Wang, Guang Hui. Judicious Bisection of Hypergraphs[J]. ACTA MATHEMATICA SINICA-ENGLISH SERIES,2016,32(5):579-584. |
APA | Tang, Yu Cong,Xu, Xin,&Wang, Guang Hui.(2016).Judicious Bisection of Hypergraphs.ACTA MATHEMATICA SINICA-ENGLISH SERIES,32(5),579-584. |
MLA | Tang, Yu Cong,et al."Judicious Bisection of Hypergraphs".ACTA MATHEMATICA SINICA-ENGLISH SERIES 32.5(2016):579-584. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论