Judicious partitions of hypergraphs (Q1356017)

The authors show: Let \(G\) be a 3-uniform hypergraph with \(m\)-edges, let \(k\geq 2\) be an integer, and let \(p_1,\dots,p_k\) be nonnegative reals such that \(\sum_{i=1}^kp_i=1\). Then there is a partition \(V(G)=\bigcup_{i=1}^kV_i\) such that, for \(i=1,\dots,k\), we have \(e(V_i)\leq p_i^3m+5m^{6/7}(\log k)^{1/2}\) and \(e(\bigcup_{j=1}^iV_j)<(\sum_{j=1}^ip_j)^3m+5m^{6/7}(\log k)^{1/2}\), where \(e(V_i)\) is the total numbers of edges of \(V_i\). From this, the main result of the present paper follows easily: Let \(G\) be a 3-uniform hypergraph with \(m\)-edges and let \(k\geq 2\) be an integer. Then there is a vertex partition of \(G\) into \(k\) sets with at most \(m/k^3+5m^{6/7}(\log k)^{6/7}\) edges in each set.