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

作者：金晶^*; 许宝刚

来源：中国科学:数学 , 2019, 49(07): 1063-1074.

• 公平划分
• 一致超图
• 简单图

令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数. Fan和Hou(2017)证明了每个最大度为?的m阶图G都存在一个k部划分(V1, V2,..., Vk),使得对于任意1≤i <j≤k,都成立e(Vi∪Vj)min≤{4/k2×m+4?/k,m/k-1}+o(m7/8).令H表示最大度为?的m阶r-一致超图,本文证明H存在一个k部划分(V1, V2,..., Vk),对于任意1≤i <j≤k,满足e(Vi∪Vj)≤r-1/k-1×m+o(m);也证明当?=o(m)时, H存在一个k部划分(V1, V2,..., Vk),使得对于任意l∈[k-1]和每个l元组(Vj1,..., Vjl),有e(Vj1∪···∪Vjl)≤lr/kr/m+o(m).

• 单位
  南京师范大学泰州学院; 南京师范大学