Theorem REF  was proved previously for \(k=2\)  [1]}, \(k=3\)  [2]}, [3]}, and \(k=4\)  [4]}. The theorem is stated in terms of the number of edges \(m\) ; our lower bound constructions are for the special case when \(m=n^{1+o(1)}\)  (i.e. very sparse graphs).
