On judicious partitions of uniform hypergraphs

doi:10.1016/j.jcta.2016.02.004

CSpace > 应用数学研究所

	On judicious partitions of uniform hypergraphs
	Hou, Jianfeng 1; Wu, Shufei 1; Yan, Guiying2
	2016-07-01
发表期刊	JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN	0097-3165
卷号	141 页码:16-32
摘要	Bollobas and Scott showed that the vertices of a graph of m edges can be partitioned into k sets such that each set contains at most m/k(2) o(m) edges. They conjectured that the vertices of an r-uniform hypergraph, where r > 3, of m edges may likewise be partitioned into k sets such that each set contains at most m/kr o(m) edges. In this paper, we prove the weaker statement that a partition into k sets can be found in which each set contains at most m/(k-1)(r)+r(1/2) +o(m) edges. Some partial results on this conjecture are also given. (C) 2016 Elsevier Inc. All rights reserved.
关键词	Uniform hypergraph Judicious partition Azuma-Hoeffding inequality
DOI	10.1016/j.jcta.2016.02.004
语种	英语
资助项目	NSFC[11331003]
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000374432400003
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/22658
专题	应用数学研究所
通讯作者	Hou, Jianfeng
作者单位	1.Fuzhou Univ, Ctr Discrete Math, Fujian 850003, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Hou, Jianfeng,Wu, Shufei,Yan, Guiying. On judicious partitions of uniform hypergraphs[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A,2016,141:16-32.
APA	Hou, Jianfeng,Wu, Shufei,&Yan, Guiying.(2016).On judicious partitions of uniform hypergraphs.JOURNAL OF COMBINATORIAL THEORY SERIES A,141,16-32.
MLA	Hou, Jianfeng,et al."On judicious partitions of uniform hypergraphs".JOURNAL OF COMBINATORIAL THEORY SERIES A 141(2016):16-32.