CSpace
Judicious Bisection of Hypergraphs
Tang, Yu Cong1; Xu, Xin1; Wang, Guang Hui2
2016-05-01
Source PublicationACTA MATHEMATICA SINICA-ENGLISH SERIES
ISSN1439-8516
Volume32Issue:5Pages:579-584
AbstractJudicious 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.
KeywordPartition judicious bisection hypergraph
DOI10.1007/s10114-016-4736-8
Language英语
WOS Research AreaMathematics
WOS SubjectMathematics, Applied ; Mathematics
WOS IDWOS:000373583200006
PublisherSPRINGER HEIDELBERG
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/22460
Collection中国科学院数学与系统科学研究院
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
2.Shandong Univ, Sch Math, Jinan 250100, Peoples R China
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Tang, Yu Cong]'s Articles
[Xu, Xin]'s Articles
[Wang, Guang Hui]'s Articles
Baidu academic
Similar articles in Baidu academic
[Tang, Yu Cong]'s Articles
[Xu, Xin]'s Articles
[Wang, Guang Hui]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Tang, Yu Cong]'s Articles
[Xu, Xin]'s Articles
[Wang, Guang Hui]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.