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

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

令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].