DIMACS Focus on Discrete Probability Seminar


Title:

The concentration of the chromatic number of random graphs

Speaker:

Michael Krivelevich
Tel Aviv University, Israel

Place:

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

Time:

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

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