We prove the asymptotically best possible result that, for every integer k 2, every 3-uniform graph with m edges has a vertex-partition into k sets such that each set contains at most (1+o(1)) mÂk 3 edges. We also consider related problems and conjecture a more general result.
1997 Academic Press
1. INTRODUCTION AND RESULTS
Given a graph G with m edges and an integer k 2, it is easy to see that there is some vertex-partition of G into k sets such that at most mÂk edges of G have both vertices in the same set (consider a random partition). Equivalently, G contains a k-partite subgraph with at least kmÂ(k&1) edges. In general, this is close to best possible, as can be seen by considering complete graphs; however, a number of authors have given more precise bounds in terms of the order and size of G. Edwards [8, 9], improving upon a result of Erdo s (see [10, 11]), proved the best possible result that every graph of order n and size m contains a bipartite subgraph with at least mÂ2+(n&1)Â4 edges. Recently, first Erdo s, Gya rfa s, and Kohayakawa [13] and then Alon [2] found considerably simpler proofs and extensions of this result. Andersen, Grant, and Linial [1] and Erdo s, Faudree, Pach, and Spencer [12] have given lower bounds for the maximal size of a k-partite subgraph. The problem of determining the maximal size of a k-partite subgraph is NP-complete (see [14]) and has led to a great deal of work on partitioning algorithms.
A large k-partite subgraph corresponds to a partition into k sets such that the total number of edges contained in the sets is small. However, what happens if we want the number of edges inside each set to be small? Thus instead of minimizing one quantity we now seek to minimize k quantities simultaneously. In a random partition into k sets, we expect mÂk 2 edges inside each set; we cannot in general demand less than this in every set, since any partition of K n into k sets has at least (1+o(1))( n 2 )Âk 2 edges article no. TA962744 15 0097-3165Â97 25.00