Coloring sparse hypergraphs

Abstract

Fix $k\ge 3$, and let $G$ be a $k$-uniform hypergraph with maximum degree $\Delta$. Suppose that for each $l=2,...,k-1$, every set of l vertices of G is in at most ${\Delta }^{(k-l)/(k-1)}/f$ edges. Then the chromatic number of $G$ is $O((\Delta /\log f{)}^{1/(k-1)})$. This extends results of Frieze and the second author and Bennett and Bohman. A similar result is proved for 3-uniform hypergraphs where every vertex lies in few triangles. This generalizes a result of Alon, Krivelevich, and Sudakov, who proved the result for graphs. Our main new technical contribution is a deviation inequality for positive random variables with expectation less than 1. This may be of independent interest and have further applications.