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 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 eV1.p2m..+pm/2.....+o(m...) and eV2.q2m..+qm/2.....+o(m...) for . = o(m2/3). This is sharp for complete graphs up to the error term o(m...). For an integer k . 2, let f k(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if f k(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 improve the results of Bollobás and Scott.