ACO The ACO Seminar (2010-2011)

Sept. 9 3:30pm, Wean 8220
Amin Coja-Oghlan, Warwick Mathematics Institute
The chromatic number of random graphs with moderate average degrees

Abstract:

Achlioptas and Naor determined the chromatic number of the random graph G(n,p) with average degree np=O(1) up to an additive error of one. In this talk I'm going to show how their techniques can be combined with other methods such as concentration results to obtain the chromatic number for np less than n^{1/4}.

This is joint work with Konstantinos Panagiotou and Angelika Steger.


Back to the ACO seminar


Back to the ACO home page