DIMACS Focus on Discrete Probability Seminar


The concentration of the chromatic number of random graphs


Michael Krivelevich
Tel Aviv University, Israel


DIMACS Center, Seminar Room 431, CoRE Building
Busch Campus, Rutgers University


3:30 - 4:30 PM
Thursday, December 12, 1996

We prove that every constant a>1/2 the chromatic number of the random graph G(n,p) with p=n^{-a} is almost surely concentrated in two consecutive values. This implies that for any b<1/2 and any integer valued function r(n)=O(n^b) there exists a function p(n) such that the chromatic number of G(n,p(n))is precisely(!) r(n) almost surely.

This is a joint work with Noga Alon.

Document last modified on November 27, 1996