Title: The Chromatic Number of the Random Graph G(n,1/2)
Speaker: Humberto Montalvan, Rutgers University
Date: Wednesday, April 29, 2009 12:00pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
The aim of this talk is to present a proof of the amazing fact that almost always the random graph G(n,1/2) has chromatic number (n/(2*log_2(n)))*(1+o(1)). Naturally one has to show that two inequalities hold. I will give Bollobas' original proof (dating back to 1988) of the harder inequality, using martingales.