What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable?


Thanks in advance. 



Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?
The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.


More precisely, he shows that


$$ 2\left\lceil \frac{k}{3}\right\rceil \left\lfloor \frac{2k}{3}\right\rfloor^2 < m(k) \leq \binom{2k+1}{3}$$


where the implied constants are absolute. The lower bound follows from a simple probabilistic argument -- colour all the vertices randomly, and then recolour a few necessary vertices to remove the small number of monochromatic edges which remain. The upper bound is just the number of edges of the complete 3-uniform hypergraph on $2k+1$ vertices, which is clearly not $k$-colourable


<http://www.tau.ac.il/~nogaa/PDFS/Publications/Hypergraphs%20with%20high%20chromatic%20number.pdf>


