Coloring H-free Hypergraphs
Tom Bohman, ALAN M. FRIEZE, Dhruv Mubayi · arXiv (Cornell University) · 2009
Fix $r \ge 2$ and a collection of $r$-uniform hypergraphs $\cH$. What is the minimum number of edges in an $\cH$-free $r$-uniform hypergraph with chromatic number greater than $k$. We investigate this question for various $\cH$. Our results include the following: An $(r,l)$-system is an $r$-uniform hypergraph with every two edges sharing at most $l$ vertices. For $k$ sufficiently large, the minimum number of edges in an $(r,l)$-system with chromatic number greater than $k$ is at most $c(k^{r-1}\log k)^{l/(l-1)}$, where $$c