Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We sh...Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We show that if m;（G） = pqm-δ, then there exists a bipartition V;, V;of G such that e（V;） ≤ p;m-δ + p（m/2）;+ o（√m） and e（V;） ≤ q;m-δ + q（m/2）;+ o（√m） for δ = o(m;). This is sharp for com;lete graphs up to the error term o（√m）. For an integer k ≥ 2, let fk（G） denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk（G） =（1-1/k）m + α,then G admits a k-partition such that each vertex class spans at most m/k;-Ω(m/k;) edges forα = Ω（m/k;）. Both of the above im;rove the results of Bollob′as and Scott.展开更多
基金Supported by NSFC(Grant No.11671087)New Century Programming of Fujian Province(Grant No.JA14028)
文摘Let G =（V, E） be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m;（G） be the minimum of qe（V;） + pe（V;） over partitions V = V;∪ V;, where e（V;） denotes the number of edges spanned by V;. We show that if m;（G） = pqm-δ, then there exists a bipartition V;, V;of G such that e（V;） ≤ p;m-δ + p（m/2）;+ o（√m） and e（V;） ≤ q;m-δ + q（m/2）;+ o（√m） for δ = o(m;). This is sharp for com;lete graphs up to the error term o（√m）. For an integer k ≥ 2, let fk（G） denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk（G） =（1-1/k）m + α,then G admits a k-partition such that each vertex class spans at most m/k;-Ω(m/k;) edges forα = Ω（m/k;）. Both of the above im;rove the results of Bollob′as and Scott.
