# 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