Coloring uniform sparse hypergraphs
by
Alexandr Kostochka
UIUC
Coauthors: M. Kumbhat and V. Rodl

A hypergraph is simple if it has no 2-cycles, or, equivalently, if no two distinct edges share more than one vertex. A hypergraph is b-simple if no two distinct edges share more than b vertices.

In their seminal paper introducing the Local Lemma, Erdös and Lovász gave impressive upper and lower bounds on the maximum chromatic number of r-uniform hypergraphs with bounded maximum edge degree. Based on this, they also gave such bounds on the maximum chromatic number of r-uniform hypergraphs with bounded size.

Upper bounds were later somewhat improved by Radhakrishnan and Srinivasan and by Z. Szabó. We show how to somewhat more strengthen such upper and lower bounds for chromatic number at least 4. We also extend bounds for simple hypergraphs to b-simple hypergraphs. The talk is based on results joint with M. Kumbhat and V. Rödl.

Date received: May 7, 2009