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.
1
-
$\begingroup$ 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. $\endgroup$– Thomas BloomCommented Jun 9, 2015 at 22:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
answered Jun 9, 2015 at 22:23
-
2$\begingroup$ 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}$. $\endgroup$– domotorpCommented Jun 10, 2015 at 12:22
-
2$\begingroup$ 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. $\endgroup$ Commented Jun 10, 2015 at 12:45