Improvements of the obvious lower bounds on the independence
number of (hyper)graphs have had impact on problems in discrete
geometry, coding theory, number theory and combinatorics. One of the
most famous examples is the result of Komlos-Pintz-Szemeredi (1982) on
the independence number of 3-uniform hypergraphs which made important
progress on the decades old Heilbronn problem in combinatorial geometry.
We give a sharp upper bound on the chromatic number of simple k-uniform
hypergraphs that implies the above result as well as more general
theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and
Duke-Lefmann-Rodl. Our proof technique is inspired by work of Johansson
on graph coloring and uses the semi-random or nibble method. This is
joint work with Alan Frieze.
Copyright. All Rights Reserved.