Constructions of sparse uniform hypergraphs with high chromatic number

A random construction gives new examples of simple hypergraphs with high chromatic number that have few edges and/or low maximum degree. In particular, for every integers k ≥ 2, r ≥ 2, and g ≥ 3, there exist r ‐uniform non‐ k ‐colorable hypergraphs of girth at least g with maximum degree at most ⌈ r k r ‐1 ln k ⌉. This is only 4 r 2 ln k times greater than the lower bound by Erdős and Lovász (Colloquia Math Soc János Bolyai 10 (1973), 609–627) that holds for all hypergraphs (without restrictions on girth). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010