# Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

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.

• If the $m(k)$ denotes the minimum number of edges of a 3-uniform hypergraph not $k$-colourable, then a straightforward application of the probabilistic method gives $k^2\ll m(k) \ll k^5$, I believe. – Thomas Bloom Jun 9 '15 at 22:14

## 1 Answer

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

• Not like it would change the order of magnitude from $\Theta(k^3)$, but your upper bound is not optimal, it should be ${2k-1\choose 3}$. – domotorp Jun 10 '15 at 12:22
• Corrected, thanks! (I also realised that technically the $k$ needs shifting up by 1, if we're considering a graph that is not $k$-colourable. – Thomas Bloom Jun 10 '15 at 12:45