##### Department of Mathematics,

University of California San Diego

****************************

### Math 295 - Mathematics Colloquium

## Dhruv Mubayi

## Coloring Simple Hypergraphs

##### Abstract:

\indent 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. 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.

Host: Jacques Verstraete

### February 10, 2011

### 3:00 PM

### AP&M 6402

****************************