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$
  • $\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 Bloom Jun 9 '15 at 22:14
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
    $\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 '15 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$ – Thomas Bloom Jun 10 '15 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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