Departmental Colloquium
Dhruv Mubayi
UIC
Coloring Simple Hypergraphs
Abstract: The problem of determining the independence number
of hypergraphs has tight connections to questions in discrete geometry,
coding theory, number theory, theoretical computer science 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. I will begin by explaining this problem and some of these connections. I will then describe a recent result which gives a sharp upper bound on the chromatic number of simple
k-uniform hypergraphs. The talk will be accessible to a general mathematical audience, including graduate students.
Friday February 4, 2011 at 3:00 PM in SEO 636