Coloring Simple Hypergraphs


Dhruv Mubayi University of Illinois at Chicago Dept. of Mathematics, Statistics, and Computer Science 322 Science


Wednesday, 11 August 2010 (All day)


  • AG-69

Many problems in number theory, discrete geometry, coding theory and combinatorics can be phrased as problems about finding the independence number of certain hypergraphs. 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.

After a brief introduction to these topics, I will show an upper bound on the chromatic number of certain hypergraphs. This implies the above result on independence number as well as more general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and Duke-Lefmann-Rodl. The proof technique is inspired by work of Johansson on graph coloring and uses the semi-random or nibble method. This talk will be accessible to a general mathematical audience.