Coloring sparse hypergraphs

Fix $k \geq 3$, and let $G$ be a $k$-uniform hypergraph with maximum degree $Δ$. Suppose that for each $l = 2, ..., k-1$, every set of l vertices of G is in at most $Δ^{(k-l)/(k-1)}/f$ edges. Then the chromatic number of $G$ is $O( (Δ/\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.

No reviews yet.

No comments yet.