Biased Partitions and Judicious k-Partitions of Graphs

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.

Let G =(V, E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1-p, let m_p(G) be the minimum of qe(V_1) + pe(V_2) over partitions V = V_1 ∪ V_2, where e(V_i) denotes the number of edges spanned by V_i. We show that if m_p(G) = pqm-δ, then there exists a bipartition V_1, V_2 of G such that e(V_1) ≤ p^2m-δ + p(m/2)^(-1/2)+ o(√m) and e(V_2) ≤ q^2m-δ + q(m/2)^(-1/2) + o(√m) for δ = o(m^(2/3)). This is sharp for com_plete 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^2-Ω(m/k^(7.5)) edges forα = Ω(m/k^6). Both of the above im_prove the results of Bollob′as and Scott.