Judicious partitions of weighted hypergraphs

doi:10.1007/s11425-015-5039-8

CSpace > 应用数学研究所

	Judicious partitions of weighted hypergraphs
	Xu Xin; Yan GuiYing; Zhang Yao
	2016-03-01
发表期刊	SCIENCE CHINA-MATHEMATICS
ISSN	1674-7283
卷号	59 期号:3 页码:609-616
摘要	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.
关键词	judicious partition balanced bipartition weighted hypergraph
DOI	10.1007/s11425-015-5039-8
语种	英语
资助项目	National Natural Science Foundation of China[11371355] ; National Natural Science Foundation of China[11471193]
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied ; Mathematics
WOS记录号	WOS:000369948900014
出版者	SCIENCE PRESS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/22021
专题	应用数学研究所
通讯作者	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.