超图与图公平划分的l-元组  

Bounds for l-tuples in judicious partition of hypergraphs and graphs

作　　者：金晶[1,2] 许宝刚[2] Jing Jin;Baogang Xu

机构地区：[1]南京师范大学数学科学学院,南京210023 [2]南京师范大学泰州学院,泰州225300

出　　处：《中国科学：数学》2019年第7期1063-1074,共12页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11571180和11331003);江苏省高校自然科学基金(批准号:17KJB110010)资助项目

摘　　要：令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数。 Fan和Hou(2017)证明了每个最大度为△的m阶图G都存在一个k部划分(V1, V2,..., Vk),使得对于任意1≤i<j≤k,都成立e(Vi∪Vj)≤min{4/k^2m+4△/k,m/k-1}+o(m^7/8)。令H表示最大度为△的m阶r-一致超图,本文证明H存在一个k部划分(V1,V2...,Vk),对于任意1≤i<j≤k,满足e(Vi∪Vj)≤r-1/k-1m+o(m);也证明当△=o(m)时,HH存在一个k部划分(V1,V2...,Vk),使得对于任意l∈[k-1]和每个l元组(Vj1,...,Vj1),有e(Vj1∪…∪Vj1)≤l^r/k^rm+o(m)。For a subset S of vertex set of a graph(or a hypergraph), e(S) denotes the number of edges with all their ends in S. Fan and Hou(2017) proved that every graph G with m edges and maximum degree △ admits a k-partition(V1, V2,..., Vk) such that e(Vi ∪ Vj) min{4/k2×m +4△/k,m/(k-1)}+ o(m7/8) for each pair of 1 ≤i <j≤ k.Let H be an r-uniform hypergraph with m edges and maximum degree△. In this paper, we show that H admits a k-partition(V1,..., Vk) such that e(Vi ∪ Vj)≤(r-1)/(k-1)×m + o(m) for each pair of 1 ≤i<j≤ k, and show that if △= o(m) then H admits a k-partition(V1,..., Vk) such that e(Vj1∪···∪ Vjl)≤(l^r)/(k^r)×m + o(m) for each l-tuple(Vj1,...,Vjl) with 1≤ l≤ k-1, and d(Vi)≥(1 + o(1))(1-(1-1/k)^r)m for each i ∈[k].

关 键 词：公平划分 一致超图 简单图 

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