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

Date: |
Wednesday, 11 Aug 2010 (all day) |

Venue: |
AG-69 |

(Scan to add to calendar)

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.