Zero-sum partition theorems for graphs (Q1338423)

Let \(\phi(G,k)\) denote the smallest integer \(m\) so that the vertices of the hypergraph \(G\) can be partitioned into \(m\) cells \(V_ 1,\dots, V_ m\) so that for each \(i= 1,\dots, m\), \(e(V_ i)\equiv 0\pmod k\), where \(e(V_ i)\) denotes the number of edges in the subhypergraph induced by \(V_ i\). Clearly \(\phi(G,k)\) is bounded above by the chromatic number of \(G\). This paper is devoted to the proofs of the following three results: Theorem 1. Let \(r, q\geq 2\) be positive integers. (1) There exists a constant \(t(q,r)\), depending only on \(q\) and \(r\), such that \(\phi(H,q)\leq t(q,r)\), for every \(r\)-uniform hypergraph \(H\). (2) If \(r= 2\), \(q= 2^ k\) then \(t(q,2)= 2q- 1\). Theorem 2. If \(r= 2\), \(q= p^ n\), \(p\) an odd prime, then \[ t(q,2)\leq {3\over 2} (q- 1)- {(2(q- 1)- 1)^{{1\over 2}}\over 4}+ {9\over 8}. \] Theorem 3. \(t(3,2)= 3\) and \(4\leq t(5,2)\leq 5\).