Judicious partitions of weighted hypergraphs

doi:10.1007/s11425-015-5039-8

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Judicious partitions of weighted hypergraphs
	Xu Xin; Yan GuiYing; Zhang Yao
刊名	SCIENCE CHINA-MATHEMATICS
	2016-03-01
卷号	59 期号:3 页码:609-616
关键词	judicious partition balanced bipartition weighted hypergraph
ISSN号	1674-7283
DOI	10.1007/s11425-015-5039-8
英文摘要	Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and a be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollobas and Scott: Does there exist a bipartition such that each class meets edges of total weight at least \ ? We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes. In particular, it is shown that any graph G with m edges has a partition V-1,...,V (k) such that each vertex set meets at least edges, which answers a related question of Bollobas and Scott.
资助项目	National Natural Science Foundation of China[11371355] ; National Natural Science Foundation of China[11471193]
WOS研究方向	Mathematics
语种	英语
出版者	SCIENCE PRESS
WOS记录号	WOS:000369948900014
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/22020]
专题	应用数学研究所
通讯作者	Yan GuiYing
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Xu Xin,Yan GuiYing,Zhang Yao. Judicious partitions of weighted hypergraphs[J]. SCIENCE CHINA-MATHEMATICS,2016,59(3):609-616.
APA	Xu Xin,Yan GuiYing,&Zhang Yao.(2016).Judicious partitions of weighted hypergraphs.SCIENCE CHINA-MATHEMATICS,59(3),609-616.
MLA	Xu Xin,et al."Judicious partitions of weighted hypergraphs".SCIENCE CHINA-MATHEMATICS 59.3(2016):609-616.