Judicious partitions of weighted hypergraphs  

作　　者：XU Xin YAN Gui Ying ZHANG Yao 

机构地区：[1]Academy of Mathematics and Systems Science, Chinese Academy of Sciences

出　　处：《Science China Mathematics》2016年第3期609-616,共8页中国科学：数学（英文版）

基　　金：National Natural Science Foundation of China (Grant Nos. 11371355 and 11471193)

摘　　要：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 α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollob′as and Scott： Does there exist a bipartition such that each class meets edges of total weight at least （w_1-α）/2＋（2w_2）/3？ 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（1-（1-1/k）~2）m ＋ o（m） edges, which answers a related question of Bollobás and Scott.让 G 是有为 i = 的尺寸 i 的边的加权的 hypergraph 1， 2。让 wi 表示尺寸 i 的边的全部的重量并且一是尺寸 1 的一个边的最大的重量。我们学习 Bollob

关 键 词：judicious partition balanced bipartition weighted hypergraph 

分 类 号：O157.5[理学—数学] O178[理学—基础数学]