5
$\begingroup$

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.

$\endgroup$
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$ Jun 9, 2015 at 22:14

1 Answer 1

7
$\begingroup$

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

$\endgroup$
2
  • 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$
    – domotorp
    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$ Jun 10, 2015 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.