__
TR03-073 | 11th June 2003 00:00
__

#### The Lovasz number of random graph

**Abstract:**
We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$

of the independence number and the corresponding relaxations of the

chromatic number on random graphs G(n,p). We prove that \theta is

concentrated about its mean, and that the relaxations of the chromatic

number in the case p<n^-1/2 are concentrated in intervals of constant

length. Moreover, we compute the probable value of theta(G(n,p)).

As an application, we give an improved algorithm for approximating the

independence number of in polynomial expected time. We also improve on

the analysis of an algorithm of Krivelevich for deciding whether G(n,p)

is k-colorable.